DBM-Tree: trading height-balancing for performance in metric access methods

Autor(es)

Marcos R. Vieira ^[1] ; Caetano Traina Jr. ^[2] ; Fabio J. T. Chino ^[3] ; Agma J. M. Traina ^[4]

Afiliação do(s) autor(es)

^[1] University of Sao Paulo at Sao Carlos. Institute of Mathematics and Computer Sciences - Brasil

^[2] University of Sao Paulo at Sao Carlos. Institute of Mathematics and Computer Sciences - Brasil

^[3] University of Sao Paulo at Sao Carlos. Institute of Mathematics and Computer Sciences - Brasil

^[4] University of Sao Paulo at Sao Carlos. Institute of Mathematics and Computer Sciences - Brasil

• Tipo de documento: Artigo Científico
• Fonte: Journal of the Brazilian Computer Society; v. 11, n. 3, p. 37-51, 2006-04-00.

Resumo

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. (AU)

• Processo FAPESP: 01/12536-5 - Desenvolvimento de uma ferramenta para visualizacao de consultas por similaridade em ambientes metricos.
• Beneficiário: Fabio Jun Takada Chino
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 02/07318-1 - Vislr - indexação, recuperação e visualização de dados multimídia em um sistema de arquivamento de imagens médicas
• Beneficiário: Agma Juci Machado Traina
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 01/11987-3 - Desenvolvimento de método de acesso para domínios métricos sensíveis à densidade local
• Beneficiário: Marcos Rodrigues Vieira
• Modalidade de apoio: Bolsas no Brasil - Mestrado