Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Bêdo, Marcos Vinícius Naves | - |
Autor(es): dc.creator | Jasbick, Daniel Leonardo | - |
Data de aceite: dc.date.accessioned | 2024-07-11T17:31:13Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T17:31:13Z | - |
Data de envio: dc.date.issued | 2019-12-10 | - |
Data de envio: dc.date.issued | 2019-12-10 | - |
Data de envio: dc.date.issued | 2018 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/12483 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/751963 | - |
Descrição: dc.description | 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. | - |
Descrição: dc.description | 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. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | openAccess | - |
Direitos: dc.rights | http://creativecommons.org/licenses/by-nc-nd/3.0/br/ | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Computação | - |
Título: dc.title | Revisitando VP-Trees: estruturas de complexidade de busca bub-linear em espaços métricos | - |
Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: