The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article propose une nouvelle méthode pour réduire le coût des recherches du plus proche voisin dans les espaces métriques. De nombreux index de recherche de similarité divisent récursivement une région en sous-régions à l'aide de pivots et construisent un index arborescent. La plupart des index récemment développés se concentrent sur l’élagage des objets et ne prêtent pas beaucoup d’attention à l’équilibrage des arbres. En conséquence, des index ayant une structure arborescente déséquilibrée peuvent être construits et le coût de recherche est dégradé. Nous proposons un index de recherche de similarité appelé Partitioning Capacité (PC) Tree. Il sélectionne le pivot optimal au niveau du PC qui quantifie l'équilibre des régions partitionnées par un pivot ainsi que l'efficacité estimée de l'élagage de recherche par le pivot. En conséquence, PCTree réduit le coût de recherche pour diverses distributions de données. Nous avons comparé expérimentalement PCTree avec quatre index utilisant des données synthétiques et cinq ensembles de données réels. Les résultats expérimentaux montrent que PCTree réduit avec succès le coût de recherche.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
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
Copier
@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},}
Copier
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 -