A cluster-based iterative search approach over HNSW

• Marco Antônio Vieira UFRGS
• Anderson R. Tavares UFRGS

DOI: https://doi.org/10.5753/eramiars.2025.16779

Resumo

Approximate Nearest Neighbor Search (ANNS) algorithms use various techniques to perform an approximate similarity search on vector databases, exchanging the optimality of exhaustive search for drastic time savings. The HNSW algorithm for ANNS uses a hierarchical Proximity Graph (PG) to reduce the number of hops during search. However, HNSW cannot produce diverse results because it uses a single entry point. In this work, we propose iHNSW, a novel cluster-based approach to enable iterative search of the HNSW graph. Empirical experiments on SIFT1M, GIST, MNIST, and Fashion-MNIST vector datasets show that our approach consistently leads to an increase in recall metrics at the cost of extending search time.

Referências

Aumüller, M., Bernhardsson, E., and Faithfull, A. (2018). ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. [link].

Chen, Q., Zhao, B., Wang, H., Li, M., Liu, C., Li, Z., Yang, M., and Wang, J. (2021). Spann: Highly-efficient billion-scale approximate nearest neighborhood search. NeurIPS, 34:5199–5212.

Fu, C., Xiang, C., Wang, C., and Cai, D. (2019). Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12(5):461–474.

Jayaram Subramanya, S., Devvrit, F., Simhadri, H. V., Krishnawamy, R., and Kadekodi, R. (2019). DiskANN: Fast accurate billion-point nearest neighbor search on a single node. NeurIPS, 32.

Jegou, H., Douze, M., and Schmid, C. (2010). Product quantization for nearest neighbor search. IEEE TPAMI, 33(1):117–128.

Malkov, Y., Ponomarenko, A., Logvinov, A., and Krylov, V. (2014). Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61–68.

Malkov, Y. A. and Yashunin, D. A. (2018). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAMI, 42(4):824–836.

Munoz, J. V., Gonçalves, M. A., Dias, Z., and Torres, R. d. S. (2019). Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognition, 96:106970.