Revisitando VP-Trees: estruturas de complexidade de busca bub-linear em espaços métricos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorBêdo, Marcos Vinícius Naves-
Autor(es): dc.creatorJasbick, Daniel Leonardo-
Data de aceite: dc.date.accessioned2024-07-11T17:31:13Z-
Data de disponibilização: dc.date.available2024-07-11T17:31:13Z-
Data de envio: dc.date.issued2019-12-10-
Data de envio: dc.date.issued2019-12-10-
Data de envio: dc.date.issued2018-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/12483-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/751963-
Descrição: dc.descriptionConsultas 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.-
Descrição: dc.descriptionSimilarity 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/br/-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectComputação-
Título: dc.titleRevisitando VP-Trees: estruturas de complexidade de busca bub-linear em espaços métricos-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.