Lune

KDD2026Top-tier venue

PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing

Tobias Rubel, Richard Wen, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram, Jakub Lacki

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Pre-trained Embeddings for Entity Resolution: An Experimental Analysis cites Deep Entity Matching with Pre-Trained Language Models
  • Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval cites Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on18

  1. Retrieval-Augmented Generation for Knowledge-Intensive NLP TasksPatrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni et al.NeurIPS 2020 · 19,162 citations
  2. Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text RetrievalLee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang et al.ICLR 2021 · 1,547 citations
  3. Deep Entity Matching with Pre-Trained Language ModelsYuliang Li, Jinfeng Li, Yoshihiko Suhara, AnHai Doan et al.VLDB 2021 · 484 citations
  4. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional SpacesXi Zhao, Yao Tian, Kai Huang, Bolong Zheng et al.VLDB 2023 · 88 citations
  5. Pre-trained Embeddings for Entity Resolution: An Experimental AnalysisAlexandros Zeakis, George Papadakis, Dimitrios Skoutas, Manolis KoubarakisVLDB 2023 · 63 citations

Related papers

  1. Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSDHao Guo, Youyou LuOSDI 2025 · 26 citations
  2. MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor SearchSairaj Voruganti, M. Tamer ÖzsuSIGMOD 2025 · 10 citations
  3. Relative NN-Descent: A Fast Index Construction for Graph-Based Approximate Nearest Neighbor SearchNaoki Ono, Yusuke MatsuiACM MM 2023 · 14 citations
  4. CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory DisaggregationChengying Huan, Renjie Yao, Shaonan Ma, Rong Gu et al.SIGMOD 2026
  5. HEXA: A Disjoint-Subgraph-Based Indexing Framework for Approximate Nearest Neighbor Search at Billion ScaleYifei Xu, Yanyan Shen, Youmin Chen, Linpeng HuangVLDB 2026
Dusk over the sea between two cliffs drawn in fine vertical lines