PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing

The fastest indexes for Approximate Nearest Neighbor Search (ANNS) today are also the slowest to build: graph-based methods like HNSW and Vamana achieve state-of-the-art query performance but have prohibitively large construction times due to relying on random-access-heavy beam searches. In this paper, we introduce PiPNN (Pick-in-Partitions Nearest Neighbors), an ultra-scalable graph construction algorithm that avoids this ''search bottleneck'' that existing graph-based methods suffer from. PiPNN's core innovation is HashPrune, a novel online pruning algorithm which dynamically maintains sparse collections of edges. HashPrune enables PiPNN to partition the dataset into overlapping sub-problems, efficiently perform bulk distance comparisons via dense matrix multiplication kernels, and stream a subset of the edges into HashPrune. HashPrune guarantees bounded memory during index construction which permits PiPNN to build higher quality indices without the use of extra intermediate memory. Our extensive experimental study demonstrates that PiPNN builds state-of-the-art indexes up to 11.6× faster than Vamana (DiskANN) and up to 12.9× faster than HNSW. We show that these improvements extend to downstream tasks, yielding speedups of up to 1.9× for approximate k-NN graph construction. PiPNN is significantly more scalable than recent algorithms for fast graph construction. PiPNN builds indexes at least 19.1× faster than MIRAGE and 17.3× than FastKCNA while producing indexes that achieve significantly higher query throughput. PiPNN enables us to build, for the first time, high-quality ANN indexes on billion-scale datasets in under 20 minutes using a single multicore machine. An open-source implementation is available at https://github.com/ParAlg/PiPNN.