DiskANN

Overview

DiskANN is a family of approximate nearest-neighbour (ANN) search algorithms from Microsoft Research, and the open-source library that implements them. Its original goal was bold: index and search a billion vectors on a single machine with modest memory, by keeping most of the index on a solid-state drive (SSD) rather than in RAM.

Graph indexes such as HNSW give excellent speed and recall, but they keep full vectors and the graph in memory. At billion scale that can mean hundreds of gigabytes or terabytes of RAM. Compressed methods such as IVF-PQ fit in memory but tend to lose accuracy. DiskANN keeps a compressed copy of every vector in RAM for navigation, and stores the graph and full-precision vectors on SSD. A query reads only a few small blocks from disk.

An everyday analogy: a delivery driver carries a pocket map in the van (the compressed vectors in RAM) to choose which streets to try. Only when close to the right area do they open the detailed street atlas kept in the depot (the SSD) to check exact house numbers. The pocket map is rough but small; the atlas is precise but slow to consult, so they consult it as rarely as possible.

What it is

DiskANN combines a specific graph design with a memory and storage layout.

Because a node's neighbour list and its full vector sit together on disk, one read fetches both. That keeps the number of disk round trips small.

The project is now a broader library. Its repository describes it as a vector indexing library for fast, fresh and filtered search in databases, released under the MIT licence.

Where it came from

The original paper, "DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node", was presented at NeurIPS 2019. Its authors were Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy and Rohan Kadekodi. It introduced the Vamana graph and showed that a workstation with 64 GB of RAM and an inexpensive SSD could serve the billion-point SIFT1B dataset at more than 5,000 queries per second, under 3 ms mean latency and above 95% 1-recall@1 on a 16-core machine. The paper also reported indexing five to ten times more points per node than in-memory graph methods at high recall.

Later work extended the method:

• Fresh-DiskANN (2021) added support for inserting and deleting points while the index serves queries.
• Filtered-DiskANN (2023) built label filters into the graph, so queries such as "nearest neighbours with tag X" work efficiently.
• Later papers covered inner-product search and diversity-aware results.
• A VLDB 2025 paper described how DiskANN is integrated into Azure Cosmos DB for NoSQL vector search.

The code has been rewritten more than once. The current library is written mainly in Rust and is designed to be embedded in databases. The earlier C++ implementation remains available on a separate branch but is no longer actively developed. Python bindings are published as diskannpy. Several vector databases, including Milvus, offer a DiskANN-style index.

How it works

1. Build the Vamana graph

Building starts from a random graph. The algorithm then visits each point, runs a greedy search for it from the entry point, and uses the nodes it passed through as candidate neighbours. A pruning step keeps at most R neighbours per node.

The pruning rule is the key idea. A candidate is dropped if an already chosen neighbour is much closer to it, by a factor called alpha. With alpha above 1, the rule keeps some longer-range links instead of only the very nearest points. Those long links let a search cross the data in few hops, which matters when every hop may cost a disk read.

For data too large to build in memory, the paper partitions the points into overlapping clusters, builds a graph per cluster, and merges them.

2. Compress and lay out the data

Every vector is compressed with product quantization, and the codes are kept in RAM. On SSD, each node's record holds its full vector and its neighbour list, aligned to disk blocks.

3. Search

1. Start at the entry point.
2. Keep a list of the best candidates found so far, sized by a search list parameter L.
3. Expand the closest unvisited candidates in a beam, reading their records from SSD in parallel.
4. Use compressed codes in RAM to estimate distances to newly seen neighbours and update the list.
5. Use the full vectors already read from disk to re-rank candidates exactly.
6. Stop when no closer candidates remain, and return the top k.

Larger L means more nodes visited, higher recall and more disk reads.

4. Update and filter

In the fresh variant, new points are inserted with the same search-and-prune step. Deletions are marked and later consolidated by repairing the graph. In the filtered variant, labels guide both graph construction and search, so the walk stays among points that match.

Key concepts and terms

A worked example

This is an illustrative calculation.

A search team must serve 1 billion 128-dimension vectors. In float32 that is 1,000,000,000 × 512 bytes, about 512 GB, before any graph.

• An in-memory graph index would need that 512 GB plus the graph, which with 32 neighbours per node at 4 bytes each adds about 128 GB.
• With DiskANN, they keep 32-byte PQ codes in RAM: about 32 GB. Graph and full vectors, about 640 GB, go on an NVMe SSD.
• They choose R = 64 and a build list size of 100, and set alpha just above 1.
• At query time, they try L = 50, 100 and 200 and measure recall@10 against exact results on 1,000 queries. Each step up in L raises recall and adds disk reads.
• They pick the smallest L that meets their recall target, then check tail latency under load, because SSD queueing can hurt the slowest queries.

The machine needs far less RAM than an in-memory design, at the cost of depending on fast SSD.

Strengths and limitations

Strengths:

• Billion-scale search on one machine with modest RAM.
• High recall, because candidates are re-ranked with full vectors.
• Few disk round trips thanks to the long-range edges and the co-located layout.
• Variants support live updates and label filtering.
• MIT licence and active use inside databases.

Limitations:

• Performance depends heavily on SSD speed and parallel read capacity.
• Index builds at billion scale take a long time and substantial resources.
• Tail latency can rise under heavy concurrent load.
• More parameters to tune than a simple flat or IVF index.
• When data easily fits in RAM, in-memory graphs are often simpler and faster.

How it compares with alternatives

Practical guidance and best practices

1. Use DiskANN when vectors clearly will not fit in RAM; otherwise test an in-memory graph first.
2. Use NVMe SSDs with high random-read throughput and measure them before tuning.
3. Size the PQ codes so they fit comfortably in RAM with room for caching.
4. Tune L at query time against a recall target computed from exact search.
5. Measure tail latency, not only averages, under realistic concurrency.
6. Cache nodes near the entry point to save disk reads on every query.
7. For changing data, use a fresh variant or a database that provides one, and schedule consolidation.
8. Use built-in label filtering instead of filtering results after search when filters are selective.

Common mistakes

• Running on network-attached or slow disks and blaming the algorithm.
• Comparing with in-memory indexes at different recall levels.
• Choosing PQ codes so small that navigation becomes inaccurate.
• Ignoring build time and memory when planning index rebuilds.
• Filtering after search, which can leave too few results for strict filters.

Frequently asked questions

Why can DiskANN use so little memory?

It keeps only compressed codes and a small cache in RAM. The graph and full vectors sit on SSD, and a search reads just a handful of node records. The compressed codes are good enough to steer the search, and full vectors fix the final ranking.

What is the Vamana graph?

It is DiskANN's graph construction method. It links each point to a limited set of neighbours, using a pruning factor alpha that keeps some longer-range links. Those links shorten search paths, which reduces disk reads.

Does DiskANN support updates?

The original algorithm built a static index. Fresh-DiskANN added inserts and deletes while serving, with deletions repaired in a later consolidation step.

Can DiskANN filter by metadata?

Filtered-DiskANN builds label awareness into the graph so that filtered queries stay efficient. Support depends on the system you use it through.

Is DiskANN only for disks?

No. Vamana graphs can also be used fully in memory, and the original paper reported them to be competitive there too. The disk layout is what makes very large indexes affordable.

Glossary

• SSD: solid-state drive, fast storage with no moving parts.
• NVMe: an interface that lets SSDs handle many parallel reads.
• Out-degree: number of edges leaving a node.
• Entry point: node where every search begins.
• Consolidation: repairing a graph after deletions.
• Tail latency: response time of the slowest queries, such as the 99th percentile.
• Embedding: a vector representing an item's meaning, see embeddings.

Summary

DiskANN is Microsoft Research's graph-based approach to approximate nearest-neighbour search at very large scale. It keeps compressed vectors in RAM to guide a beam search over a Vamana graph stored on SSD, then re-ranks with full vectors read from disk. This allows billion-point indexes on a single machine with modest memory. Later variants add live updates and filtering, and the library now targets embedding in databases. Use it when data far exceeds memory, invest in fast SSDs, and tune by measuring recall and tail latency on your own workload. See hybrid search for how vector search fits into retrieval systems.

Related

It belongs to Vector indexes in my stack, under Generative AI and LLMs. Others in the same group: