Research map / Graph learning / Graph algorithms and clustering
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, Rohan Kadekodi
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| single one-shot Vamana index replaced by merged index of overlapping shards (ablation) | DiskANN on SIFT1B · SIFT1B bigann | search latency at target recall: up to 20% extra latency | Hurt |
| merged index enables building under 64GB RAM instead of ~1100GB (ablation) | Vamana on SIFT1B · SIFT1B bigann | peak memory during build: ~1100GB -> under 64GB | Improved |
| Vamana with alpha > 1 versus HNSW and NSG (alpha = 1) | graph index · SIFT1M-scale, 98% 5-recall@5 | hops to converge: 2-3x fewer hops | Improved |
| Vamana indexing versus HNSW and NSG for in-memory search | graph index · SIFT1M, GIST1M, DEEP1M | recall vs latency | Improved |
| Vamana indexing versus HNSW and NSG | DEEP1M indexing · DEEP1M | index build time: 149s vs 219s (HNSW) vs 480s (NSG) | Improved |
| add a second indexing pass with alpha >= 1 over the dataset (ablation) | Vamana · graph construction | graph quality | Improved |
| initialize from random graph instead of empty graph (ablation) | Vamana · graph construction | graph quality | Improved |
Closest papers by meaning
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.89)
- MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search (NeurIPS 2026 · similarity 0.87)
- Prune, Don’t Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search (NeurIPS 2026 · similarity 0.86)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.86)
- Results of the Big ANN: NeurIPS’23 competition (NeurIPS 2025 · similarity 0.85)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
