%0 Journal Article
%T DBM-Tree: trading height-balancing for performance in metric access methods
%A Vieira
%A Marcos R.
%A Traina Jr.
%A Caetano
%A Chino
%A Fabio J. T.
%A Traina
%A Agma J. M.
%J Journal of the Brazilian Computer Society
%D 2006
%I Springer
%R 10.1007/BF03192381
%X metric access methods (mam) are employed to accelerate the processing of similarity queries, such as the range and the k-nearest neighbor queries. current methods, such as the slim-tree and the m-tree, improve the query performance minimizing the number of disk accesses, keeping a constant height of the structures stored on disks (height-balanced trees). however, the overlapping between their nodes has a very high influence on their performance. this paper presents a new dynamic mam called the dbm-tree (density-based metric tree), which can minimize the overlap between high-density nodes by relaxing the height-balancing of the structure. thus, the height of the tree is larger in denser regions, in order to keep a tradeoff between breadth-searching and depth-searching. an underpinning for cost estimation on tree structures is their height, so we show a non-height dependable cost model that can be applied for dbm-tree. moreover, an optimization algorithm called shrink is also presented, which improves the performance of an already built dbm-tree by reorganizing the elements among their nodes. experiments performed over both synthetic and real world datasets showed that the dbm-tree is, in average, 50% faster than traditional mam and reduces the number of distance calculations by up to 72% and disk accesses by up to 66%. after performing the shrink algorithm, the performance improves up to 40% regarding the number of disk accesses for range and k-nearest neighbor queries. in addition, the dbm-tree scales up well, exhibiting linear performance with growing number of elements in the database.
%K metric access method
%K metric tree
%K indexing
%K similarity queries.
%U http://www.scielo.br/scielo.php?script=sci_abstract&pid=S0104-65002006000100004&lng=en&nrm=iso&tlng=en