Source: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
NeurIPS 2019 paper introducing the Vamana graph and an SSD-resident ANN index that serves a billion vectors from one 64 GB machine.
Contents
- What: research paper, NeurIPS 2019
- Authors: Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, Rohan Kadekodi (Microsoft Research)
- Date: 2019
- Original: proceedings.neurips.cc (abstract)
Summary
DiskANN challenges the assumption that ANN indexes must live in RAM. Its Vamana graph is built with a pruning rule controlled by a parameter alpha; alpha > 1 keeps longer-range edges, shrinking the number of hops, which matters because each hop on SSD is a random read. Product-quantized vectors stay in RAM to steer the search, while the graph and full-precision vectors sit on SSD and are used to re-rank.
Key claims
- Vamana parameters: max out-degree R, search list size L, pruning factor alpha. Build makes two passes, first alpha = 1, then the user alpha.
- HNSW and NSG implicitly use alpha = 1; the tunable alpha gives Vamana a better degree/diameter trade-off and 2 to 3 times fewer hops for SSD serving.
- Billion-scale build: k-means into about 40 overlapping clusters (each point assigned to its 2 nearest), build per-cluster graphs in memory, merge by edge union.
- Layout: PQ codes (e.g. 32 bytes per point) in RAM; each point’s full vector plus its neighbor list stored together on SSD, so re-ranking costs no extra reads.
- BeamSearch fetches several frontier nodes per round; widths of 2 to 8 balance latency and throughput.
- SIFT1B on a 64 GB, 16-core machine: over 5,000 queries per second, under 3 ms mean latency, 95%+ 1-recall@1. Comparable-memory IVF/PQ methods plateaued near 50% 1-recall@1.
- In the high-recall regime it serves roughly 5 to 10 times more points per node than in-memory graph indexes.