ANTIPOLE TREE INDEXING AND GRAPHGREPVF: DATA STRUCTURES AND ALGORITHMS FOR OPTIMIZATION AND SEARCHING PROBLEMS IN METRIC SPACES AND GRAPHS

There has been increasing interest in building search/index structures to perform similarity search over high-dimensional data, e.g., image databases, document collections, time-series databases, and genome databases. A similarity search problem involves a collection of objects (e.g., documents, images) which are characterized by a collection of relevant features and represented as points in a high-dimensional attribute space. The first part of this book will present a new hierarchical clustering algorithm called Antipole Clustering. The algorithm partitions the set of data objects in clusters such that each one has diameter approximately less than a given value. The algorithm returns a tree structure called Antipole Tree in which the leaves are the final clusters. The second part of this book will present, GraphGrepVF, an application-independent method for querying a database of graphs in order to find all the occurrences of a given subgraph. Many applications in industry, science and engineering share this problem, and increasing the size of the database requires efficient structure searching algorithms.