The Pulse
UMD’s PiPNN Builds a Billion-Vector Index in Under 20 Minutes
University of Maryland and Google Research researchers developed PiPNN, an algorithm that builds an approximate nearest-neighbor index for a billion vectors in under 20 minutes. The system speeds index construction, but its billion-scale te
AI.info Team · Written with AI · fact-checked ·
Graph-based search indexes are built to answer nearest-neighbor queries quickly, but constructing them can take hours or days on billion-point datasets. PiPNN, a new algorithm from University of Maryland and Google Research collaborators, targets that bottleneck: its authors say it can build a high-quality index for a billion items in under 20 minutes. The speed comes with a significant hardware qualification: the billion-scale tests ran on a cloud machine with 288 virtual CPUs and 2.2 terabytes of memory.
PiPNN trades graph-by-graph searching for batches
Approximate nearest-neighbor search helps systems retrieve items similar to a query, including documents and recommendation candidates represented as vectors. Established graph-based methods such as HNSW and Vamana build connections by searching a partially constructed graph as each point is added. The PiPNN paper identifies those repeated, irregular memory accesses as a major source of long construction times.
PiPNN instead divides the data into small, overlapping groups, calculates distances among points within each group in batches, and selects candidate connections for the index. Its HashPrune method filters redundant edges as candidates arrive, keeping the graph sparse without holding every candidate in memory at once. “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,” write Tobias Rubel, Richard Wen, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram and Jakub Łącki in their paper. The authors of “PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing”
The speedup depends on the comparison
Across the paper’s benchmarks, PiPNN builds indexes up to 12.9 times faster than HNSW and up to 11.6 times faster than Vamana. Those are peak results, not a single speedup across every dataset: the paper reports average improvements of 10.4 times over HNSW and 6.32 times over Vamana. The authors say PiPNN’s indexes reach comparable quality to leading methods in their tests, while an additional construction pass can improve quality at the cost of more build time.
The billion-point experiments used four datasets, including BigANN, DEEP, MS-SPACEV and MS-Turing. For those runs, the team used a Google Cloud c4-highmem-288 machine with 288 vCPUs and 2.2 terabytes of DRAM. That is one machine, as the authors describe it, but not a typical server configuration.
Memory remains a deployment constraint
The paper also shows limits in the comparison set: MIRAGE and FastKCNA exceeded the available 2.2 terabytes of memory and could not be evaluated on the billion-scale datasets. The result therefore demonstrates strong construction speed against methods that completed those runs, rather than a billion-scale win over every competing approach. The University of Maryland’s October 20 account of the work also says the team is exploring ways to shift operations to cheaper storage and to adapt PiPNN for continuously arriving data.
The same university account reports that Microsoft is working to integrate the open-source code into its systems, while the researchers are discussing possible adoption with Meta and NVIDIA. Those efforts would test whether the faster build process and its memory demands fit production systems, where data changes and index refreshes can matter as much as query speed.