DBM-tree: metric access method sensitive to local density data

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.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