Paper Information | SBC BOOKS

Fill in your paper information

Language (*)

Title (*)

Keywords (*)

Abstract (*)

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

Pages (*)

File Link

English Information

Title

Keywords

Abstract

Hierarchical Navigable Small World (HNSW) indexes provide stateof-the-art performances for approximate k-nearest neighbor (kNN) queries. However, binding the approximate search quality with the characterization of the HNSW construction heuristic remains an open issue. This article investigates if result diversification can bridge this gap by discussing a new HNSW construction strategy based on a local, diversification-driven partitioning principle. Accordingly, we extend the HNSW kNN search algorithm to support result diversification. Experimental evaluations on ANN-Benchmark showed while diversification-based partitioning improves the search Recall, standard construction still yields higher throughput. We examined this trade-off through the lens of Local Intrinsic Dimensionality (LID), stratifying the datasets into quartiles. This evaluation indicated the throughput difference shrinks with the LID, with the diversification-based construction yielding a higher Recall in every LID-based manifold. Such outcomes suggest that HNSW long edges’ tuning may depend on the LID manifold.

(*) To change the order drag the item to the new position.

Authors

#	Name
1	Mauro Weber(mauro_weber@id.uff.br)
2	João Leite(joaovitorleite@id.uff.br)
3	Daniel de Oliveira(danielcmo@ic.uff.br)
4	Marcos Bedo(marcosbedo@id.uff.br)

(*) To change the order drag the item to the new position.

Reference

#	Reference
1	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.
2	Amsaleg, L., Chelly, O., Houle, M., Kawarabayashi, K., Radovanovic, M., and Treratanajaru, W. (2019). Intrinsic dimensionality estimation within tight localities. In ICDM.
3	Aumueller, M., Bernhardsson, E., and Faithfull, A. (2020). Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Info. Sys., 87:101374.
4	Aumueller, M. and Ceccarello, M. (2021). The role of local dimensionality measures in benchmarking nearest neighbor search. Info. Sys., 101:101807.
5	Drosou, M., Jagadish, H., Pitoura, E., and Stoyanovich, J. (2017). Diversity in big data: A review. Big Data, 5:73–84.
6	He, J., Kumar, S., and Chang, S.-F. (2012). On the difficulty of nearest neighbor search. In ICML, pages 41–48.
7	Houle, M. (2013). Dimensionality, discriminability, density and distance distributions. In ICDM, pages 468–473. IEEE.
8	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.
9	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.
10	Kucuktunc, O. and Ferhatosmanoglu, H. (2013). λ-diverse nearest neighbors browsing for multidimensional data. TKDE, 25(3):481–493.
11	Li, L., Xu, J., Li, Y., and Cai, J. (2021). Hctree+: A workload-guided index for approximate knn search. Info. Sc., 581:876–890.
12	Malkov, Y. and Yashunin, D. (2016). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. TPAMI, PP.
13	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.
14	Santana, D. and Ribeiro, L. (2023). Approximate similarity joins over dense vector embeddings. In SBBD, pages 51–62. SBC.
15	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.
16	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.
17	Volnyansky, I. and Pestov, V. (2009). Curse of dimensionality in pivot based indexes. In SISAP, pages 39–46. IEEE.
18	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.
19	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.

Paper Registration

Fill in your paper information

English Information

Authors

Reference