# FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search

arXiv: https://arxiv.org/abs/2105.09613 · HTML: https://mlsanity.com/paper/2105.09613/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2021.

## Built on by (most cited first, 30 of 38)

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval](https://mlsanity.com/paper/2201.05409/) (2022)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [MicroNN: An On-device Disk-resident Updatable Vector Database](https://mlsanity.com/paper/2504.05573/) (2025)
- [Pancake: Hierarchical Memory System for Multi-Agent LLM Serving](https://mlsanity.com/paper/2602.21477/) (2026)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search](https://mlsanity.com/paper/2505.17152/) (2025)
- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [Curator: Efficient Indexing for Multi-Tenant Vector Databases](https://mlsanity.com/paper/2401.07119/) (2024)
- [Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search](https://mlsanity.com/paper/2405.12207/) (2024)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [RAGDoll: Efficient Offloading-based Online RAG System on a Single GPU](https://mlsanity.com/paper/2504.15302/) (2025)
- [Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors](https://mlsanity.com/paper/2507.21989/) (2025)
- [QVCache: A Query-Aware Vector Cache](https://mlsanity.com/paper/2602.02057/) (2026)
- [How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?](https://mlsanity.com/paper/2512.06200/) (2025)
- [What It Costs to Compose, Rebuild, and Correct Precomputed Memory](https://mlsanity.com/paper/2608.30647/) (2026)
- [EigenLI: Spectral Approximations to Late Interaction](https://mlsanity.com/paper/2609.07561/) (2026)
- [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025)
- [Learning Filter-Aware Distance Metrics for Nearest Neighbor Search with Multiple Filters](https://mlsanity.com/paper/2511.04073/) (2025)
- [Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN](https://mlsanity.com/paper/2512.09331/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)
- [Mycelium-Index: A Streaming Approximate Nearest Neighbor Index with Myelial Edge Decay, Traffic-Driven Reinforcement, and Adaptive Living Hierarchy](https://mlsanity.com/paper/2604.11274/) (2026)
- [IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer](https://mlsanity.com/paper/2605.17415/) (2026)
- [CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces](https://mlsanity.com/paper/2605.23887/) (2026)
- [EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates](https://mlsanity.com/paper/2606.00734/) (2026)

## Abstract (arXiv)

Approximate nearest neighbor search (ANNS) is a fundamental building block in information retrieval with graph-based indices being the current state-of-the-art and widely used in the industry. Recent advances in graph-based indices have made it possible to index and search billion-point datasets with high recall and millisecond-level latency on a single commodity machine with an SSD. However, existing graph algorithms for ANNS support only static indices that cannot reflect real-time changes to the corpus required by many key real-world scenarios (e.g. index of sentences in documents, email, or a news index). To overcome this drawback, the current industry practice for manifesting updates into such indices is to periodically re-build these indices, which can be prohibitively expensive. In this paper, we present the first graph-based ANNS index that reflects corpus updates into the index in real-time without compromising on search performance. Using update rules for this index, we design FreshDiskANN, a system that can index over a billion points on a workstation with an SSD and limited memory, and support thousands of concurrent real-time inserts, deletes and searches per second each, while retaining >95% 5-recall@5. This represents a 5-10x reduction in the cost of maintaining freshness in indices when compared to existing methods.