Abstract:

Searching for similar objects in metric-space databases can be efficiently solved by using index data structures. A number of alternative sequential indexes have been proposed in the literature. This paper proposes the parallelization of a recent pivot-based index data structure which can efficiently accommodate on-line updates and reduces the number of object-to-object comparisons during searches. We assume a large collection of objects evenly distributed on the secondary memory of a set of processors and consider the parallel processing of a constant stream of queries as in the case of search engines. We present algorithms for index construction and query processing. Applications of metric-space indexes are in multimedia databases and text databases in cases such as detection of similar documents.