Please use this identifier to cite or link to this item: https://app.uff.br/riuff/handle/1/12483
Title: Revisitando VP-Trees: Estruturas de Complexidade de Busca Sub-linear em Espaços Métricos
Authors: Jasbick, Daniel Leonardo
metadata.dc.contributor.advisor: Bêdo, Marcos Vinícius Naves
Issue Date: 2018
Abstract: Consultas por similaridade constituem um paradigma base para o tratamento de dados que só possuem uma relação de distância entre si. Esse paradigma suporta diversas tarefas computacionais modernas, tais como agrupamento, classificação baseada em distância e recuperação de dados por conteúdo. Na prática, duas das mais utilizadas consultas por similaridade são as buscas por abrangência e vizinhança. Vantage-Point Trees (VP-Trees) permitem executar consultas por similaridade com eficiência ao organizar o espaço de busca de forma hierárquica e disjunta, o que torna a complexidade média da busca sub-linear. No entanto, o desempenho de buscas em VP-Trees depende da escolha adequada de parâmetros de inicialização, a saber: (i) a forma de selecionar elementos pivôs e (ii) a permissão para se ter excesso de elementos em nós-folha, o que garante o balanceamento da árvore. Este trabalho consiste na análise da construção e consulta de VP-Trees com o objetivo de avaliar o impacto dos parâmetros de inicialização no desempenho de buscas por abrangência e vizinhança. Após uma discussão teórica detalhada, avaliamos seis combinações dos parâmetros de inicialização em quatro conjuntos de dados reais. Os resultados em nossos experimentos indicam que: (i) o uso de métodos de seleção de pivôs tem maior impacto que o balanceamento da árvore, com relação ao desempenho da estrutura em buscas indexadas, (ii) critérios de consulta distintos são executados melhor por índices com parametrizações diferentes, (iii) o método de escolha de pivôs por variância máxima de distâncias obteve os melhores resultados, (iv) consultas com maior seletividade são melhor tratadas por árvores desbalanceadas e consultas com menor seletividade são melhor tratadas por árvores balanceadas, e (v) o método de escolha de pivôs por fecho-convexo apresentou maior facilidade em gerar estruturas balanceadas, na comparação com outros métodos. Todas as técnicas e algoritmos estudados foram implementados na ferramenta VP-Viewer, que permite a visualização de VP-Trees, inspeção de distribuição de distâncias em nós-diretório e análise dos caminhos percorridos no índice para consulta por similaridade.
metadata.dc.description.abstractother: Similarity searching is a foundational paradigm for the handling of distance-only data. The paradigm supports a broad variety of computational tasks, such as clustering, distance-based classification, and content-based retrieval. In practice, two of the most requested similarity searches are the range and neighborhood queries. Vantage-Point Trees (VP-Trees) execute similarity searches efficiently by organizing the search space in a hierarchical and disjoint fashion. As a result, the average indexed search complexity becomes sub-linear. However, VP-Trees’ query performance depends on the suitable choice of initialization parameters, namely: (i) Pivot selection method, and (ii) Leaf-node overflow criterion, which ensures VP-Tree balance. This study addresses the VP-Tree indexing and querying for the assessment of the initialization parameters impact regarding both range and neighborhood queries. We provide a theoretical discussion on VP-Tree main routines and evaluate six distinct groups of initialization parameters on real-world datasets. Experimental results indicate (i) pivot selection impacts similarity queries deeper than tree balance, (ii) different similarity queries are executed better by distinct VP-Trees parameterizations, (iii) maximum variance-based pivot selection outperformed other selection methods regarding VP-Tree searching, (iv) unbalanced trees are more suitable than balanced trees for more selective queries, and (v) convex hull-based pivot selection is more likely to generate balanced trees, in comparison to other selection methods. All reviewed strategies are implemented on VP-Viewer, a tool that enables visualization of VP-Trees, inspection of distance-distribution within tree nodes and exploration of VP-Tree query paths.
URI: https://app.uff.br/riuff/handle/1/12483
Appears in Collections:PCL - Trabalhos de Conclusão de Curso - Santo Antônio de Pádua

Files in This Item:
File Description SizeFormat 
TFC_ DANIEL_LEONARDO_JASBICK.pdf1.97 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons