How to improve the pruning ability of dynamic metric access methods

Caetano Traina Jr., Agma J. M. Traina, Roberto F. Santos Filho, Christos Faloutsos

Abstract

Complex data retrieval is accelerated using index structures, which organize the data in order to prune comparisons between data during queries. In metric spaces, comparison operations can be specially expensive, so the pruning ability of indexing methods turns out to be specially meaningful. This paper shows how to measure the pruning power of metric access methods, and defines a new measurement, called "prunability," which indicates how well a pruning technique carries out the task of cutting down distance calculations at each tree level. It also presents a new dynamic access method, aiming to minimize the number of distance calculations required to answer similarity queries. We show that this novel structure is up to 3 times faster and requires less than 25% distance calculations to answer similarity queries, as compared to existing methods. This gain in performance is achieved by taking advantage of a set of global representatives. Although our technique uses multiple representatives, the index structure still remains dynamic and balanced.
BibTeX
@inproceedings{jr2002how,
  author = {Caetano Traina Jr. and Agma J. M. Traina and Roberto F. Santos Filho and Christos Faloutsos},
  title = {{How to improve the pruning ability of dynamic metric access methods}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2002},
  doi = {10.1145/584792.584831},
}

Loading related content...

Figure