Zonal HNSW: Scalable Approximate Nearest Neighbor Search for Billion-Scale Datasets
A Akhil, G. Siva Shankar · 2025
Effectively navigating billion-scale datasets for Approximate Nearest Neighbor (ANN) search remains a critical challenge in modern data science. We introduce Zonal Hierarchical Navigable Small World (ZHNSW), a novel framework designed to provide superior scalability and performance. While leveraging insights from established algorithms like HNSW, FAISS, and Annoy, ZHNSW introduces a key innovation: zonal partitioning. This technique decomposes the high-dimensional search space into multiple, smaller, localized HNSW graphs, thereby reducing complexity and enabling significant parallelization of search operations. Complementing this, ZHNSW employs adaptive zone selection strategies—encompassing fixed fraction, distance thresholding, and heuristic-based methods—which dynamically optimize the search process by focusing on the most relevant data regions. Extensive experiments on challenging benchmarks such as SIFT1B, DEEP1B, GLOVE-1.2M, and MUSIC100M, utilizing the NVIDIA DGX A100 platform, confirm ZHNSW’s advantages. It demonstrates up to 3× improvement in search speed, a high recall@10 of 98.7%, and a 29% decrease in index size when compared against state-of-the-art alternatives, solidifying ZHNSW as a robust and highly efficient solution for contemporary data-intensive similarity search applications.