PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing

PiPNN (Pick-in-Partitions Nearest Neighbors, pronounced “Pippin”) is a current line of work on fast, hardware-friendly construction of proximity graphs for Approximate Nearest Neighbor Search (ANNS) and k-nearest neighbor (k-NN) graphs. PiPNN builds state-of-the-art graph indices 12–13× faster than Vamana (DiskANN) and HNSW on CPUs and up to 50× faster than state-of-the-art GPU methods—constructing billion-scale indices in 15–20 minutes on a single machine.

Why were previous graph-based indexing methods slow?

Graph-based indices (such as HNSW and Vamana) deliver the best query throughput and recall for vector search, but building them is notoriously slow. Traditional builders insert points by running greedy beam searches over the partially constructed graph, which chases random pointers across memory, underutilizes modern CPUs and GPUs, and takes hours or days on billion-vector datasets.

How PiPNN works

PiPNN eliminates graph search during construction altogether. At a high level, we partition the points into overlapping clusters, perform leaf building within each cluster to select candidate edges, and combine the selected edges using an online pruning algorithm:

• Hardware-friendly dense linear algebra: Both overlapping partitioning of the points and candidate edge selection during leaf building are reduced to dense linear algebra (GEMM) and top-K operations—making the core computation extremely friendly to modern CPUs, GPUs, and hardware accelerators.
• Quantized fused kernels & GPUs: We quantize vectors to low precision, fuse top-K extraction directly into the matrix kernel (avoiding materializing distance matrices), and flatten recursive partitioning into segmented GPU batches.
• Simple and extremely-efficient k-NN graph building: The PiPNN algorithm also enables directly building high-recall k-NN graphs without resorting to beam search on an ANNS index, running up to 13× faster on CPUs and 6.6× faster on GPUs against the prior state-of-the-art—building a billion-scale 10-NN graph in under 16 minutes.

Where PiPNN is used

Although PiPNN was only introduced in 2026, it has already been adopted across major industrial vector search libraries, databases, and scientific computing stacks:

• Google (Ginger): Official C++ implementation in Google Ginger, used at Google Research for billion-scale ANNS indexing and fast k-NN graph construction in clustering and data-mining pipelines.
• Microsoft Research (DiskANN): Integrated into DiskANN as a high-throughput graph-index build backend for in-memory and disk-based indices.
• Meta (FAISS): Shipped in FAISS for fast graph-based index construction.
• NVIDIA (cuVS): GPU graph construction and CAGRA index building in NVIDIA cuVS.
• Qdrant (Qdrant): Integrated into Qdrant’s HNSW index builder, with GPU acceleration.
• Ant Group (VSAG): CPU and CUDA GPU PiPNN graph construction in Ant Group’s VSAG vector engine.
• Apache Lucene & Redis: Active upstream work for HNSW level-0 graph construction in Apache Lucene and bulk vector indexing in Redis.
• Single-cell genomics (Scanpy): Adopted in the Python/Rust single-cell ecosystem to accelerate k-NN graph construction for UMAP and Leiden clustering on large cell atlases.

Awards

• Best Research Paper Award — ACM SIGKDD 2026
• Best Paper Award (and Selected for Oral Presentation) — VecDB Workshop @ VLDB 2026
• 1st Place — SISAP 2026 Indexing Challenge (Task 1)

Research team

• Tobias Rubel (UMD)
• Richard Wen (UMD)
• Guy E. Blelloch (CMU & Google Research)
• Laxman Dhulipala (UMD & Google Research)
• Lars Gottesbüren (Google Research)
• Rajesh Jayaram (Google Research)
• Jakub Łącki (Google Research)
• Vahab Mirrokni (Google Research)

Publications

Namesake

PiPNN was named after Laxman’s family’s wonderful corgi, Pippin: