The search functionality is under construction.
The search functionality is under construction.

Margin-Based Pivot Selection for Similarity Search Indexes

Hisashi KURASAWA, Daiji FUKAGAWA, Atsuhiro TAKASU, Jun ADACHI

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Information Vol.E93-D No.6 pp.1422-1432
Publication Date
2010/06/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E93.D.1422
Type of Manuscript
Special Section PAPER (Special Section on Info-Plosion)
Category
Multimedia Databases

Authors

Keyword