• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
10.11606/D.55.2004.tde-27072004-141623
Document
Author
Full name
Marcos Rodrigues Vieira
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2004
Supervisor
Committee
Traina Junior, Caetano (President)
Lifschitz, Sergio
Nonato, Luis Gustavo
Title in Portuguese
DBM-tree: método de acesso métrico sensível à densidade local
Keywords in Portuguese
árvore métrica
espaço métrico
índice
método de acesso métrico
Abstract in Portuguese
Um espaço métrico é definido por um conjunto de objetos e uma função de distância métrica, que é utilizada para avaliar o nível de similaridade entre estes objetos. Isto permite a elaboração de Métodos de Acesso Métricos (MAMs) capazes de responder consultas por similaridade nesses conjuntos em um tempo reduzido. Em geral, esses MAMs são materializados através de uma estrutura hierárquica chamada de árvore métrica. Normalmente essas árvores são mantidas balanceadas, pois isto tende a manter a altura da árvore mínima, reduzindo o número de acessos a disco necessários para responder às consultas. No entanto, é difícil manter as estruturas balanceadas sem a existência de sobreposição entre os nós que cobrem regiões de alta densidade de objetos. O efeito disto é a degradação do tempo das consultas, pois várias subárvores devem ser analisadas para compor as consultas. Em outras palavras, minimizar a sobreposição entre os nós aumenta a eficiência das árvores métricas. Um meio efetivo para isto é flexibilizar o balanceamento das árvores métricas. Este trabalho apresenta um novo MAM dinâmico, chamado de DBM-tree (Density-Based Metric tree), que permite flexibilizar o balanceamento da estrutura, minimizando o grau de sobreposição entre os nós em regiões densas e, conseqüentemente, aumentando o seu desempenho para responder às consultas. Essa flexibilização é ajustada pelo usuário e é rigidamente controlada pela estrutura. A profundidade da árvore é maior em regiões de alta densidade, procurando um equilíbrio entre o número de acessos a disco para avaliar múltiplas subárvores e para a busca em profundidade em cada subárvore. A DBM-tree possui um algoritmo de otimização chamado de DBM-Slim-Down, que melhora o desempenho das árvores através da reorganização de elementos entre os seus nós. Os experimentos feitos com dados reais e sintéticos mostram que a DBM-tree supera em desempenho os MAMs tradicionais. Ela é, em média, 50% mais rápida que os MAMs tradicionais e reduz o número de acessos a disco e cálculos de distância em até 50%. Depois de executado o algoritmo DBM-Slim-Down, o seu desempenho melhorou em até 30% para as consultas por abrangência e aos vizinhos mais próximos. Ainda, a DBM-tree é escalável considerando tempo total de processamento, número de acessos a disco e de cálculos de distância em relação ao tamanho do conjunto de dados indexado.
Title in English
DBM-tree: metric access method sensitive to local density data
Keywords in English
index
metric access method
metric space
metric tree
Abstract in English
A metric space is defined as a set of objects and a metric distance function that is used to measure the similarity between these objects. It allows the development of Metric Access Methods (MAMs) that are able to answer similarity queries in these datasets quickly. Usually these MAMs are materialized through a hierarchical structure called metric trees. These trees are kept balanced because it tends to maintain the height of the tree small, aiming to reduce the number of disk access required to answer queries. However, it is difficult to maintain the tree balanced without overlapping nodes covering a large number of objects, leading to the degradation of query performance. In other words, reducing the overlap among nodes increases the performance of metric trees. A possible solution is to relax the need to keep metric trees balanced. This work presents a new dynamic MAM called DBM-tree (Density-Based Metric tree), which changes the rule that imposes a rigid balancing policy, allowing a small amount of unbalancing in some regions of it. This unbalancing minimizes the degree of overlapping among some high-density nodes and, consequently, increases query answering performance. The amount of relaxation is set by the user and is strongly enforced in the tree. The height of the tree is higher in high-density regions, in order to keep a balance between searching in various subtrees and searching deeply in each subtree. The DBM-tree has an optimization algorithm called DBM-Slim-Down that improves the performance in trees through reorganizing the elements among its nodes. The experiments performed over synthetic and real-world datasets showed that the DBM-tree outperforms the traditional MAMs. The DBM-tree is, in average, 50% faster than traditional MAMs and reduces the number of distance calculations and disk accesses up to 50%. After executing the DBM-Slim-Down algorithm, the performance achieves improvements up to 30% for range and k-nearest neighbor queries. Moreover, the DBM-tree is scalable regarding time, number of disk accesses and distance calculations.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
DBM-tree_Vieira04.pdf (6.18 Mbytes)
Publishing Date
2004-07-29
 
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • VIEIRA, Marcos R., et al. A visual framework to understand similarity queries and explore data in Metric Access Methods [doi:10.1504/IJBIDM.2010.036125]. International Journal of Business Intelligence and Data Mining [online], 2010, vol. 5, n. 4, p. 370-397.
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2019. All rights reserved.