Adicionando suporte à diversificação de resultados em índices HNSW considerando espaços de baixa e alta dimensionalidade

• Mauro Weber Universidade Federal Fluminense
• João Silva-Leite Universidade Federal Fluminense
• Lúcio F. D. Santos Instituto Federal do Norte de Minas Gerais
• Daniel de Oliveira Universidade Federal Fluminense
• Marcos Bedo Universidade Federal Fluminense

DOI: https://doi.org/10.5753/sbbd.2024.240618

Resumo

Í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.

Palavras-chave: HNSW, kNN, Consultas kNN Aproximadas, Alta Dimensionalidade, Dimensionalidade Intrínseca Local

Referências

Amsaleg, L., Chelly, O., Furon, T., Girard, S., Houle, M., Kawarabayashi, K.-i., and Nett, M. (2018). Extreme-value-theoretic estimation of local intrinsic dimensionality. DMKD, 32(6):1768–1805.

Amsaleg, L., Chelly, O., Houle, M., Kawarabayashi, K., Radovanović, M., and Treratanajaru, W. (2019). Intrinsic dimensionality estimation within tight localities. In ICDM.

Aumüller, M., Bernhardsson, E., and Faithfull, A. (2020). Ann-benchmarks: A bench-marking tool for approximate nearest neighbor algorithms. Info. Sys., 87:101374.

Aumüller, M. and Ceccarello, M. (2021). The role of local dimensionality measures in benchmarking nearest neighbor search. Info. Sys., 101:101807.

Drosou, M., Jagadish, H., Pitoura, E., and Stoyanovich, J. (2017). Diversity in big data: A review. Big Data, 5:73–84.

He, J., Kumar, S., and Chang, S.-F. (2012). On the difficulty of nearest neighbor search. In ICML, pages 41–48.

Houle, M. (2013). Dimensionality, discriminability, density and distance distributions. In ICDM, pages 468–473. IEEE.

Jasbick, D., Dutra Santos, L., de Oliveira, D., and Bedo, M. (2020). Some branches may bear rotten fruits: Diversity browsing vp-trees. In SISAP, pages 140–154. Springer.

Jasbick, D., Santos, L., Azevedo-Marques, P., Traina, A., de Oliveira, D., and Bedo, M. (2023). Pushing diversity into higher dimensions: The LID effect on diversified similarity searching. Info. Sys., 114:102166.

Kucuktunc, O. and Ferhatosmanoglu, H. (2013). λ-diverse nearest neighbors browsing for multidimensional data. TKDE, 25(3):481–493.

Li, L., Xu, J., Li, Y., and Cai, J. (2021). Hctree+: A workload-guided index for approximate knn search. Info. Sc., 581:876–890.

Malkov, Y. and Yashunin, D. (2016). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. TPAMI, PP.

Peng, Z., Zhang, M., Li, K., Jin, R., and Ren, B. (2022). Speed-ann: Low-latency and high-accuracy nearest neighbor search via intra-query parallelism.

Santana, D. and Ribeiro, L. (2023). Approximate similarity joins over dense vector embeddings. In SBBD, pages 51–62. SBC.

Santos, L., Oliveira, W., Ferreira, M., Traina, A., and Traina Jr, C. (2013). Parameter-free and domain-independent similarity search with diversity. In SSDBM, pages 1–12.

Shimomura, L. C., Oyamada, R. S., Vieira, M. R., and Kaster, D. S. (2021). A survey on graph-based methods for similarity searches in metric spaces. Info. Sys., 95:101507.

Volnyansky, I. and Pestov, V. (2009). Curse of dimensionality in pivot based indexes. In SISAP, pages 39–46. IEEE.

Wang, M., Xu, X., Yue, Q., and Wang, Y. (2021). A comprehensive survey and experimental comparison of graph-based approximate nn search. PVLDB, 14(11):1964–1978.

Xian, J., Teofili, T., Pradeep, R., and Lin, J. (2024). Vector search with OpenAI embeddings: Lucene is all you need. In ICWSDM, pages 1090–1093.