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

Hisashi KURASAWA; Daiji FUKAGAWA; Atsuhiro TAKASU; Jun ADACHI

doi:10.1587/transinf.E94.D.504

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

Hisashi KURASAWA, Daiji FUKAGAWA, Atsuhiro TAKASU, Jun ADACHI

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E94-D No.3 pp.504-514

Publication Date: 2011/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E94.D.504

Type of Manuscript: Special Section PAPER (Special Section on Data Engineering)

Category

Cite this

Copy

Hisashi KURASAWA, Daiji FUKAGAWA, Atsuhiro TAKASU, Jun ADACHI, "Optimal Pivot Selection Method Based on the Partition and the Pruning Effect for Metric Space Indexes" in IEICE TRANSACTIONS on Information, vol. E94-D, no. 3, pp. 504-514, March 2011, doi: 10.1587/transinf.E94.D.504.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.504/_p

Copy

@ARTICLE{e94-d_3_504,
author={Hisashi KURASAWA, Daiji FUKAGAWA, Atsuhiro TAKASU, Jun ADACHI, },
journal={IEICE TRANSACTIONS on Information},
title={Optimal Pivot Selection Method Based on the Partition and the Pruning Effect for Metric Space Indexes},
year={2011},
volume={E94-D},
number={3},
pages={504-514},
abstract={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.},
keywords={},
doi={10.1587/transinf.E94.D.504},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Optimal Pivot Selection Method Based on the Partition and the Pruning Effect for Metric Space Indexes
T2 - IEICE TRANSACTIONS on Information
SP - 504
EP - 514
AU - Hisashi KURASAWA
AU - Daiji FUKAGAWA
AU - Atsuhiro TAKASU
AU - Jun ADACHI
PY - 2011
DO - 10.1587/transinf.E94.D.504
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2011
AB - 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.
ER -