DBM-tree: método de acesso métrico sensível à densidade local (2004)
- Authors:
- Autor USP: VIEIRA, MARCOS RODRIGUES - ICMC
- Unidade: ICMC
- Subjects: ENGENHARIA DE SOFTWARE; ESPAÇOS MÉTRICOS; ALGORITMOS E ESTRUTURAS DE DADOS
- Language: Português
- Abstract: 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 emregiõ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
- Imprenta:
- Publisher place: São Carlos
- Date published: 2004
- Data da defesa: 28.05.2004
-
ABNT
VIEIRA, Marcos Rodrigues. DBM-tree: método de acesso métrico sensível à densidade local. 2004. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2004. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-27072004-141623/. Acesso em: 19 abr. 2024. -
APA
Vieira, M. R. (2004). DBM-tree: método de acesso métrico sensível à densidade local (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-27072004-141623/ -
NLM
Vieira MR. DBM-tree: método de acesso métrico sensível à densidade local [Internet]. 2004 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-27072004-141623/ -
Vancouver
Vieira MR. DBM-tree: método de acesso métrico sensível à densidade local [Internet]. 2004 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-27072004-141623/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
