Optimal Pivot Selection Method Based on the Partition and the Pruning Effect for Metric Space Indexes

Hisashi KURASAWA
Daiji FUKAGAWA
Atsuhiro TAKASU
Jun ADACHI

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D    No.3    pp.504-514
Publication Date: 2011/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.504
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Data Engineering)
Category: 
Keyword: 
pivot selection,  similarity search,  metric space,  

Full Text: PDF>>
Buy this Article


Summary: 
This paper proposes a new method to reduce the cost of nearest neighbor searches in metric spaces. Many similarity search indexes recursively divide a region into subregions by using pivots, and construct a tree-structured index. Most of recently developed indexes focus on pruning objects and do not pay much attention to the tree balancing. As a result, indexes having imbalanced tree-structure may be constructed and the search cost is degraded. We propose a similarity search index called the Partitioning Capacity (PC) Tree. It selects the optimal pivot in terms of the PC that quantifies the balance of the regions partitioned by a pivot as well as the estimated effectiveness of the search pruning by the pivot. As a result, PCTree reduces the search cost for various data distributions. We experimentally compared PCTree with four indexes using synthetic data and five real datasets. The experimental results shows that the PCTree successfully reduces the search cost.