Adicionando suporte à diversificação de resultados em índices HNSW considerando espaços de baixa e alta dimensionalidade - Weber, Mauro; Silva-Leite, João; Santos, Lúcio F. D.; de Oliveira, Daniel; Bedo, Marcos (Anais do Simpósio Brasileiro de Banco de Dados (SBBD); 2024: Anais do XXXIX Simpósio Brasileiro de Bancos de Dados, 2024)
Índices do tipo Hierarchical Navigable Small World (HNSW) apresentam desempenhos estado-da-arte em consultas aproximadas aos k-vizinhos mais próximos (kNN). Não obstante, caracterizar a estratégia de construção destes índices e seu impacto na qualidade da busca aproximada ainda é um desafio em aberto. Este artigo investiga como a diversificação de resultados pode contribuir para esta caracterização ao discutir uma nova construção para o HNSW que utiliza a perspectiva dos objetos de consulta para gerar regiões diversificadas. Nesse sentido, o algoritmo de busca kNN do HNSW também é estendido para dar suporte à diversificação de resultados. Avaliações experimentais no ANN-Benchmarks mostram que, embora o particionamento com diversidade melhore substancialmente a qualidade da busca, a estratégia HNSW atinge uma maior taxa de vazão. Para entender melhor esse balanço, foi utilizado o conceito da Dimensionalidade Intrínseca Local (LID) para estratificar os dados em quartis de dificuldade. Essa avaliação mostrou que a diferença de vazão entre as duas construções diminui com a LID, enquanto que a qualidade das consultas permanece maior no particionamento por diversidade. Esses resultados sugerem que o ajuste do HNSW depende da distribuição de distâncias.