DBM*-Tree: An efficient metric acces method

No Thumbnail Available
Date
2007
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Scopus
Abstract
In this paper we propose a new dynamic Metric Access Method (MAM) called DBM*-Tree, which uses precomputed distances to reduce the construction cost avoiding repeated calculus of distance. Making use of the pre-calculated distances cost of similarity queries are also reduced by taking various local representative objects in order to increment the pruning of irrelevant elements during the query. We also propose a new algorithm to select the suitable subtree in the insertion operation, which is an evolution of the previous methods. Empiric tests on real and synthetic data have shown evidence that DBM*-Tree requires 25 % less average distance computing than Density Based Metric Tree (DBM-Tree) which is one of the most efficient and recent MAM found in the literature. © Copyright 2007 ACM.
Description
Keywords
Algorithms , Cost functions , Data reduction , Information retrieval , Measurement theory , Query processing , Metric access methods , Multidimensional index , Similarity information retrieval , Similarity queries , Trees (mathematics)
Citation
URI
https://hdl.handle.net/20.500.12590/15914
Collections
Artículos - Ciencias de la Computación