Margin-Based Pivot Selection for Similarity Search Indexes

作者：Kurasawa Hisashi^*; Fukagawa Daiji; Takasu Atsuhiro; Adachi Jun

来源：IEICE Transactions on Information and Systems, 2010, E93D(6): 1422-1432.

DOI：10.1587/transinf.E93.D.1422

• similarity search
• indexing
• metric space

When developing an index for a similarity search in metric spaces, how to divide the space for effective search pruning is a fundamental issue. We present Maximal Metric Margin Partitioning (MMMP), a partitioning scheme for similarity search indexes. MMMP divides the data based on its distribution pattern, especially for the boundaries of clusters. A partitioning boundary created by MMMP is likely to be located in a sparse area between clusters. Moreover, the partitioning boundary is at maximum distances from the two cluster edges. We also present an indexing scheme, named the MMMP-Index, which uses MMMP and pivot filtering. The MMMP-Index can prune many objects that are not relevant to a query, and it reduces the query execution cost. Our experimental results show that MMMP effectively indexes clustered data and reduces the search cost. For clustered data in a vector space, the MMMP-Index reduces the computational cost to less than two thirds that of comparable schemes.

• 出版日期2010-6