DiskANN

DiskANN stores the proximity graph and compressed vectors directly on SSD, not in RAM. This design fundamentally breaks the memory wall, allowing a single machine with limited DRAM to serve indices that are an order of magnitude larger than main memory. During search, only a small, relevant subset of graph nodes and their full-precision vectors are paged into RAM via efficient I/O, minimizing latency.

The core indexing algorithm, Vamana, builds a graph with a constant out-degree optimized for fast, greedy traversal. Unlike HNSW's layered structure, Vamana constructs a single, high-quality graph with a carefully controlled diameter. The key innovation is the robust prune step, which ensures the graph remains connected and navigable even with a limited number of edges per node, preventing search paths from getting stuck in local minima.

To minimize SSD storage and I/O, DiskANN compresses the original high-dimensional vectors using Product Quantization (PQ). The graph structure is stored alongside these compact PQ codes. During search, the query is compared against the PQ-compressed vectors for fast, approximate distance calculations. The full-precision vectors are stored separately and only accessed for the final, high-accuracy re-ranking of a small candidate set.

DiskANN employs Asymmetric Distance Computation (ADC) for its PQ-based scoring. The query vector remains in full precision, while the database vectors are represented by their PQ codes. This approach yields significantly higher recall than symmetric computation (where both are quantized) because only one side of the distance calculation is approximated, preserving more of the query's information.

The search algorithm is a beam search over the Vamana graph. To mitigate the latency of random SSD reads, DiskANN caches the visited graph nodes in a small in-memory buffer. This exploits the observation that many queries traverse similar paths in the graph, turning repeated random I/O into cache hits. The beam width parameter directly controls the trade-off between search accuracy and speed.

DiskANN operates as a two-stage pipeline. First, a fast, approximate search using the graph and PQ codes generates a candidate set. Then, the original, full-precision vectors for these candidates are read from SSD and used to compute exact distances. This re-ranking step corrects the quantization error, ensuring the final top-K results have high recall, often exceeding 95%.

A family of indexing algorithms that represent vectors as nodes in a proximity graph. DiskANN builds a single-layer graph with a carefully controlled graph degree, using greedy traversal over edges connecting similar items. Unlike HNSW's multi-layer hierarchy, DiskANN optimizes for SSD-friendly access patterns by minimizing random reads during search.

A vector compression technique that decomposes high-dimensional vectors into smaller subvectors, quantizing each independently using a distinct codebook. DiskANN uses PQ to compress full-precision vectors stored on SSD, dramatically reducing I/O during search. The compressed representation enables fast asymmetric distance computation (ADC) where the query remains uncompressed for higher accuracy.

The core graph construction algorithm behind DiskANN. Vamana builds a directed graph with a bounded maximum degree by iteratively connecting each node to a diverse set of approximate nearest neighbors. Key properties include:

• GreedySearch with a beam width parameter for robust graph traversal
• RobustPrune operation that ensures edge diversity by removing redundant connections
• Out-of-core construction that processes data in passes, never requiring the full graph in RAM

DiskANN's key innovation is reorganizing graph data for sequential SSD reads rather than random access. The graph adjacency lists and PQ-compressed vectors are stored in an interleaved layout so that a single SSD read retrieves both the neighbor IDs and their compressed vectors. This minimizes expensive I/O operations per query, typically requiring only 1-2 disk reads for high recall.

A two-stage retrieval pipeline where the SSD-based graph search retrieves a candidate set using PQ-compressed vectors, then a final re-ranking step computes exact distances using full-precision vectors cached in RAM. This architecture decouples the graph traversal cost from the final accuracy, achieving near-exact recall while keeping the working set on SSD.

The constrained search problem of finding nearest neighbors that satisfy structured metadata filters. DiskANN implements pre-filtering by generating a candidate set from the graph, then applying predicates during the beam search. For strict filters, it supports post-filtering where the graph search retrieves extra candidates that are then filtered and re-ranked, balancing recall against filter selectivity.