Defesa de Dissertação de Mestrado de Mauro Nunes Weber – 29/11/2024, 10h, por videoconferência
Link para defesa: https://meet.google.com/gvu-mths-jpd
Buscas kNN com Diversificação de Resultados em Índices HNSW
Resumo:
Com o avanço do aprendizado profundo, funções de distância podem ser usadas diretamente para comparar representações vetoriais de alta dimensionalidade, dando subsídio para a execução de consultas kNN. Índices exatos e aproximados podem ser usados para melhorar o desempenho de buscas kNN, sendo o índice Hierarchical Navigable Small World (HNSW) o estado da arte para a execução de buscas aproximadas. Não obstante, a qualidade dos resultados kNN em espaços de alta dimensionalidade ainda pode ser melhorada com o uso de critérios de busca mais sofisticados, como a diversificação por resultados baseada no conceito de Influência. A hipótese de pesquisa investigada nesta dissertação é que o HNSW pode ser estendido em dois aspectos: (i) seu princípio de particionamento de forma a contemplar o particionamento por Influência, e (ii) seu algoritmo de busca com objetivo de otimizar consultas por diversidade em espaços de alta dimensionalidade. Assim, a primeira contribuição desta dissertação é a proposta de uma nova abordagem de construção para o índice HNSW (batizada de dHNSW) com o uso de particionamento em bola ao invés de hiperplanos, enquanto que a segunda contribuição é um algoritmo de busca com diversificação de resultados para buscas aproximadas. As implementações realizadas foram avaliadas no ambiente de teste ANN-Benchmarks que possibilita a comparação direta contra o HNSW, onde foi possível observar os ganhos de qualidade trazidos pelo dHNSW com relação ao método original. Para caracterizar melhor esses ganhos, foi realizada uma avaliação estratificada com base na Dimensionalidade Intrínseca Local (LID), que permitiu uma análise detalhada dos índices em diferentes níveis de concentração de distância. Os resultados indicaram que o dHNSW não só trouxe resultados de maior qualidade, mas que alcançou um desempenho de tempo compatível com o HNSW (em termos de consultas por segundo), especialmente nos casos mais difíceis de alta dimensionalidade intrínseca. Isso se justifica porque o dHNSW produziu distribuições de arestas (distâncias) menos concentradas, melhorando a organização do espaço de busca nestes casos limite.
Abstract:
With the advancement of deep learning, distance functions can be directly used to compare high-dimensional vector representations, enabling the execution of kNN queries. Exact and approximate indices can be used to improve kNN search performance, with index Hierarchical Navigable Small World (HNSW) representing the state of the art for approximate searches. However, the quality of kNN results in high-dimensional spaces can be enhanced through more sophisticated search criteria, such as result diversification based on the concept of Influence. This dissertation hypothesizes that the HNSW index can extend in two ways: (i) by modifying its partitioning principle to incorporate partitioning by Influence, and (ii) by optimizing its search algorithm to enhance queries with diversification in high-dimensional spaces. Thus, the first contribution is a new construction approach for the HNSW index, utilizing ball-based partitioning principle (instead of hyperplane), coined dHNSW. The second contribution introduces a search algorithm that provides result diversification for approximate searches, denoted as kdNN. The proposed methods were examined within a benchmarking environment that facilitates comparison with HNSW. Observations indicate that dHNSW significantly improved the search quality in comparison to the original method. To further characterize these gains, a stratified evaluation based on Local Intrinsic Dimensionality (LID) was conducted, enabling a detailed analysis of the index behavior at different distance concentration levels. The results indicate that dHNSW not only reached higher quality results but also achieved a search performance comparable to HNSW (in terms of queries per second), particularly in challenging cases of high intrinsic dimensionality. This improvement resulted from dHNSW producing less concentrated edge (distance) distributions, thereby enhancing the organization of the search space in these critical cases.
Banca examinadora:
Prof. Marcos Vinícius Naves Bêdo, UFF – Presidente
Prof. Daniel Cardoso Moraes de Oliveira, UFF
Prof. Luiz André Portes Paes Leme, UFF
Prof. Fábio André Machado Porto, LNCC
Profa. Mirela Teixeira Cazzolato, USP