La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Optimal Pivot Selection Method Based on the Partition and the Pruning Effect for Metric Space Indexes Méthode de sélection de pivot optimale basée sur la partition et l'effet d'élagage pour les index d'espace métrique

Hisashi KURASAWA, Daiji FUKAGAWA, Atsuhiro TAKASU, Jun ADACHI

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E94-D No.3 pp.504-514
Date de publication
2011/03/01
Publicisé
ISSN en ligne
1745-1361
DOI
10.1587/transinf.E94.D.504
Type de manuscrit
Special Section PAPER (Special Section on Data Engineering)
Catégories

Auteurs

Mots-clés

Table des matières