DiskANN

Unlike in-memory algorithms like HNSW, DiskANN stores the Vamana graph index on solid-state drives, accessing only a tiny fraction of the graph during search. It exploits the high random-read IOPS of modern NVMe SSDs while minimizing the performance penalty of disk I/O. The algorithm intelligently caches only the most frequently traversed graph nodes in RAM, using a beam search that overlaps computation with asynchronous disk reads to hide latency. This design decouples dataset size from expensive DRAM capacity.

DiskANN builds a directed graph named Vamana with a crucial property: the graph diameter is small and the out-degree of each node is bounded, ensuring fast traversal. Construction uses a greedy search with a pruning strategy that eliminates edges to nodes that are already reachable via shorter paths. This creates a navigable structure where the longest path between any two points is logarithmic relative to the dataset size. The pruning parameter, alpha, controls the graph density and directly tunes the recall-latency trade-off.

To minimize storage footprint and I/O cost, DiskANN compresses the full-precision vectors stored on disk using Product Quantization (PQ). The original high-dimensional vector is split into sub-vectors, and each is independently quantized to a codebook. During search, distances are computed using asymmetric distance computation against the PQ codes, avoiding the need to decompress the full vector. This achieves a typical compression ratio of 8x to 32x with a negligible impact on recall, enabling billion-scale datasets to fit on a single server's SSDs.

DiskANN's search uses a beam search that maintains a frontier of candidate nodes. It issues asynchronous read requests for the graph neighbors of frontier nodes, overlapping I/O with distance computation. A small, dynamic LRU cache in RAM holds the graph adjacency lists of frequently visited nodes, absorbing the locality inherent in the search traversal. This cache-aware design ensures that the algorithm saturates the SSD's queue depth without blocking on individual reads, achieving sub-millisecond latency per query on billion-scale datasets.

Unlike static indexes that require costly full rebuilds, DiskANN supports incremental insertion of new vectors directly into the Vamana graph. The algorithm performs a beam search to locate the neighborhood for the new point, then updates the graph edges using the same pruning strategy from construction. This allows the index to stay current with streaming data without blocking queries. Deletions are handled via a lazy tombstone mechanism, marking nodes as invalid and reclaiming space during periodic consolidation.

DiskANN natively supports predicate-based filtering during ANN search, combining vector similarity with structured metadata constraints. The algorithm applies filters during the beam search traversal, skipping graph nodes that do not match the predicate before computing distances. This avoids the post-filtering pitfall where a query returns zero results. The implementation handles complex boolean expressions on document tags, timestamps, and categorical attributes, enabling use cases like searching within a specific date range or product category.

The foundational graph construction algorithm behind DiskANN. Vamana builds a directed graph with a constant out-degree and a long-range edge property, ensuring the graph diameter remains small. This allows a greedy search to converge in logarithmic steps. The key innovation is the pruning strategy: during construction, the algorithm connects a new node to its nearest neighbors but then prunes redundant short-range links, preserving long-range shortcuts that enable fast navigation across the entire dataset. This graph structure is what makes DiskANN's SSD-resident index viable.

Unlike in-memory ANN algorithms like HNSW, DiskANN stores the full graph index on an NVMe SSD, with only a small cache of frequently accessed nodes in RAM. The index is laid out sequentially on disk to maximize sequential read throughput rather than random I/O. A compressed representation of vector data is stored alongside the graph edges, minimizing the bytes read per hop. This design enables searching billion-scale datasets on a single commodity machine without requiring terabytes of expensive RAM.

DiskANN uses Product Quantization (PQ) to compress the full-precision vectors stored on the SSD. The original high-dimensional vector is split into sub-vectors, each quantized to a codebook. During search, only the compact PQ codes are read from disk to compute approximate distances. This drastically reduces the I/O cost per distance computation. The full-precision vector is only accessed for the final candidate re-ranking step, ensuring high recall while keeping disk bandwidth requirements low.

DiskANN employs a beam search strategy over the Vamana graph. Starting from a fixed entry point, the algorithm maintains a beam of the W closest candidates found so far. At each step, it expands the best unexplored candidate, reading its neighbors from the SSD. A critical optimization is backtracking: if the search reaches a local minimum, the algorithm can revisit previously skipped nodes. This balances exploration and exploitation, achieving high recall with a bounded number of expensive disk reads.

To mitigate SSD latency, DiskANN maintains a hotspot-aware cache of graph nodes in main memory. Frequently traversed nodes—typically those near the entry point or in dense clusters—are cached using a memory-mapped file mechanism. The caching policy is not a simple LRU; it is informed by the graph structure itself, prioritizing nodes with high out-degree and those on critical navigation paths. This hybrid RAM/SSD architecture is the core of DiskANN's cost-performance trade-off.

DiskANN supports incremental insertion without a full index rebuild. New vectors are inserted directly into the Vamana graph by finding their nearest neighbors and updating edges, with a background process periodically re-optimizing local graph regions. This is critical for production retrieval pipelines where data is continuously ingested. Combined with a log-structured merge (LSM) tree approach for deletions, DiskANN maintains query performance even as the index mutates, avoiding the downtime associated with batch-only indexing.