A cluster-based iterative search approach over HNSW - Vieira, Marco Antônio; Tavares, Anderson R. (Anais da Escola Regional de Aprendizado de Máquina e Inteligência Artificial da Região Sul (ERAMIA-RS); 2025: Anais da I Escola Regional de Aprendizado de Máquina e Inteligência Artificial da Região SulDO - 10.5753/eramiars.2025.16779, 2025)
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.