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.

1. Bibliographic Information

• Title: FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
• Authors:
  • Aditi Singh (Microsoft Research India)
  • Suhas Jayaram Subramanya (Carnegie Mellon University, work done at Microsoft Research)
  • Ravishankar Krishnaswamy (Microsoft Research India)
  • Harsha Vardhan Simhadri (Microsoft Research India)
• Journal/Conference: The paper is available on arXiv, a preprint server. It was likely prepared for a top-tier conference in data management (like VLDB, SIGMOD) or information retrieval (like SIGIR).
• Publication Year: 2021
• Abstract: The paper addresses a major limitation in state-of-the-art graph-based Approximate Nearest Neighbor Search (ANNS) indices: their static nature. While these indices excel at searching billion-point datasets on a single machine, they cannot handle real-time data updates (inserts and deletes), which are common in real-world applications like news or email search. The current industry solution is to periodically rebuild the entire index, which is extremely expensive. This paper introduces FreshDiskANN, the first graph-based ANNS system that supports real-time updates without sacrificing search performance. FreshDiskANN can index over a billion points on a commodity machine with an SSD, handle thousands of concurrent updates and searches per second, and maintain high accuracy (>95% recall). The authors claim this reduces the cost of maintaining index freshness by 5-10x compared to periodic rebuilding.
• Original Source Link:
  • arXiv: https://arxiv.org/abs/2105.09613
  • PDF: http://arxiv.org/pdf/2105.09613v1
  • Publication Status: Preprint.

2. Executive Summary

• Background & Motivation (Why):

  • Core Problem: Approximate Nearest Neighbor Search (ANNS) is crucial for modern applications like recommendation systems, image search, and natural language processing, where data is represented as high-dimensional vectors. Graph-based indices are the leading technology for static ANNS, offering exceptional speed and accuracy. However, real-world data is dynamic; new items are added, and old ones are removed constantly. Existing graph-based indices are static and cannot efficiently reflect these changes.
  • Gap in Prior Work: The standard way to handle dynamic data with graph indices is to periodically discard the old index and build a new one from scratch. This "rebuilding" is computationally intensive and time-consuming, leading to high operational costs and stale search results. Other dynamic methods, like those based on Locality Sensitive Hashing (LSH), are either too memory-hungry or too slow for high-performance scenarios.
  • Innovation: This paper introduces a method to directly update a graph-based index, allowing it to handle a continuous stream of insertions and deletions in real-time. This eliminates the need for costly periodic rebuilds.

• Main Contributions / Findings (What):

  1. Analysis of Update Failures: The paper first demonstrates why naive update strategies fail on popular graph indices like HNSW and NSG, leading to a steady degradation of search quality.
  2. FreshVamana Algorithm: They propose FreshVamana, the first graph-based index with robust update rules for insertions and deletions that maintain the graph's structural integrity and search performance over time. The key is a relaxed pruning strategy based on the α-RNG property.
  3. StreamingMerge Procedure: To scale to billion-point datasets that don't fit in memory, they design StreamingMerge, a highly efficient, two-pass algorithm to merge in-memory updates into a large, SSD-resident index. This procedure minimizes random SSD I/O, a critical bottleneck, and has a memory footprint proportional to the size of the updates, not the entire index.
  4. FreshDiskANN System: They integrate these components into a complete system, FreshDiskANN, which uses a hybrid memory/SSD architecture to provide high-throughput, low-latency search and updates on a single commodity machine. Rigorous week-long experiments show it can handle thousands of concurrent operations per second on a billion-point index while keeping search latency under 20ms and recall above 95%.

3. Prerequisite Knowledge & Related Work

• Foundational Concepts:

  • Nearest Neighbor Search (NNS): Given a dataset of points (e.g., vectors representing images), the goal is to find the point in the dataset closest to a given query point.
  • Curse of Dimensionality: In high-dimensional spaces (e.g., vectors with hundreds of dimensions), the distance between any two points tends to become uniform. This makes it computationally infeasible to find the exact nearest neighbor without comparing the query to every single point in the dataset (a linear scan), which is too slow for large datasets.
  • Approximate Nearest Neighbor Search (ANNS): Instead of finding the exact nearest neighbor, ANNS algorithms aim to find a point that is among the true closest neighbors with high probability. This trade-off allows for sub-linear search times.
  • Graph-Based ANNS: These algorithms build a graph where each data point is a node. Edges connect "close" points. To find the nearest neighbor for a query, the algorithm starts at a random or designated entry point in the graph and greedily traverses it, always moving to the neighbor closest to the query until it can't find a closer one. This is much faster than a linear scan.
  • Streaming Data / Freshness: In many applications, the dataset is not static. New data arrives continuously (e.g., new tweets, emails, products), and old data is removed. A "fresh" index is one that reflects these changes in near real-time, so search results are always up-to-date.
  • Recall: A key metric for ANNS quality. k-recall@k measures what fraction of the true k nearest neighbors are found by the algorithm in its returned list of k candidates. A recall of 1.0 (or 100%) means the search was perfect.

• Previous Works & Differentiation:

  • Tree-based Methods (kd-trees, Cover Trees): These methods partition the data space. They work well in low dimensions but their performance degrades significantly in high dimensions due to the curse of dimensionality.
  • Hashing-based Methods (LSH): These methods use hash functions that map nearby points to the same bucket with high probability. They are naturally suited for updates, as adding or removing a point is trivial. However, to achieve high recall, they require a large number of hash tables, making them very memory-intensive (PLSH) or slow if the index is on disk (SRS).
  • Quantization-based Methods (FAISS, IVFADC): These methods compress the data vectors to reduce their memory footprint, allowing billion-scale datasets to fit in RAM. They often have lower accuracy (especially for finding the single nearest neighbor) because the compression is lossy. While some support updates, their search performance is generally inferior to graph-based methods for high-recall scenarios.
  • Static Graph-based Methods (HNSW, NSG, Vamana/DiskANN): These are the state-of-the-art for static data, offering the best trade-off between speed and accuracy. However, they lack efficient update mechanisms. The main contribution of FreshDiskANN is to make this superior class of algorithms viable for dynamic, streaming data, a problem that prior work had not solved effectively.

4. Methodology (Core Technology & Implementation)

The core of the paper is a set of algorithms that allow a graph-based index to be updated without degrading its quality, and a system architecture to apply these updates efficiently to a large, disk-based index.

4.1 The Problem: Why Simple Updates Fail

The authors first demonstrate that naive approaches to updating graph indices are flawed. They experiment with two deletion policies on popular indices (HNSW, NSG, Vamana):

• Delete Policy A: Simply remove the deleted node and all its incident edges.

• Delete Policy B: When a node p is deleted, try to "heal" the graph by connecting its in-neighbors to its out-neighbors.

  As shown in Figure 1, both policies lead to a steady decline in recall over repeated cycles of deletions and insertions. This happens because these simple modifications break the carefully constructed "navigability" of the graph, making it harder for the greedy search to find the true nearest neighbors. The graph becomes too sparse or disconnected.

  该图像是图表，展示了在SIFT1M数据集上删除并重新插入5%数据批次20轮后，静态构建的HNSW、Vamana和NSG索引在两种删除策略（Delete Policy A与B）下的5-recall@5搜索召回率变化。

4.2 FreshVamana: An Updatable Graph Index

The key insight is to use a more robust graph structure that can tolerate updates. The authors build on Vamana, the graph algorithm from DiskANN, which uses a relaxed pruning rule.

• α-RNG Property: The core idea is the Relative Neighborhood Graph (RNG) property, relaxed by a parameter $α > 1$. During graph construction, an edge from node p to p'' is pruned (removed) only if there's another neighbor p' of p that is significantly closer to p'' than p is. Formally, the edge $(p, p'')$ is removed if there exists a neighbor $p'$ of $p$ such that $α \cdot d(p', p'') \leq d(p, p'')$. Using $α > 1$ (e.g., 1.2) creates denser graphs with more redundant paths, which makes them more robust to changes and ensures search paths converge quickly.

• RobustPrune (Algorithm 3): This is the central pruning procedure used in all updates. Given a node p and a set of candidate neighbors, it iteratively selects the closest candidate, adds it to p's neighborhood, and then prunes other candidates that are now "reachable" through the newly added neighbor according to the α-RNG rule. This ensures the degree of each node stays bounded by R while maintaining the graph's navigability.

• Insertion (Algorithm 2):

  1. To insert a new point p, first treat p as a query and search the existing graph to find a set of candidate neighbors V.
  2. Use RobustPrune to select the best R out-neighbors for p from V.
  3. For each new neighbor j of p, add a reciprocal (in-going) edge from j to p. If this causes j's out-degree to exceed R, run RobustPrune on j's neighborhood as well.

• Deletion (Algorithm 4):

  1. Lazy Deletion: Deletions are not processed immediately. The ID of the deleted point is added to a DeleteList. During search, points in this list are used for navigation but are filtered out from the final results.
  2. Batch Consolidation: Periodically, the deletions are consolidated in a batch. For every node p that had an edge to a deleted node v, its neighborhood is "repaired." The algorithm considers the remaining neighbors of p plus the neighbors of the deleted node v as a new candidate set. It then runs RobustPrune on this set to form a new, robust neighborhood for p.

4.3 FreshDiskANN: The Billion-Scale System

To handle datasets larger than RAM, FreshDiskANN uses a hybrid architecture.

• Components:

  • Long-Term Index (LTI): A large, SSD-resident FreshVamana index containing the bulk of the data. To save RAM, only compressed vector representations (e.g., from Product Quantization) are kept in memory for the LTI.
  • Temporary Index (TempIndex): A smaller, fully in-memory FreshVamana index that handles all new insertions. There is one read-write RW-TempIndex for incoming data and multiple read-only RO-TempIndex snapshots for stability and crash recovery.
  • DeleteList: A list of IDs for deleted points, kept in memory.

• Operations:

  • Insert(p): The new point p is added to the RW-TempIndex.
  • Delete(p): The ID of p is added to the DeleteList.
  • Search(q): The query q is sent to the LTI and all TempIndex instances in parallel. The results are merged, and any points in the DeleteList are removed before returning the final list to the user.

• StreamingMerge Procedure: This is the background process that keeps the system's memory footprint bounded. When the TempIndex instances grow too large, StreamingMerge consolidates them and the DeleteList into the SSD-based LTI. It is designed to be highly I/O-efficient.

  1. Delete Phase: It makes a first sequential pass over the LTI on SSD. For each block of nodes read into memory, it applies the deletion logic from Algorithm 4 to repair neighborhoods affected by points in the DeleteList. It uses the in-memory compressed vectors for all distance calculations to avoid reading full vectors from disk. The modified block is written to a new LTI file.

  2. Insert Phase: It processes each point p from the TempIndex instances. It searches the intermediate LTI (from the delete phase) to find candidate neighbors for p. Crucially, it does not write the required edge updates back to the SSD immediately, as this would cause a storm of slow, random writes. Instead, it stores all the required "backward" edge additions in an in-memory data structure called Δ.

  3. Patch Phase: It makes a second sequential pass over the intermediate LTI. For each block of nodes read, it applies the updates stored in Δ and runs RobustPrune if necessary. The final, updated block is written to the new LTI on disk.

     This three-phase process cleverly transforms a series of random-write-heavy updates into just two sequential passes over the large SSD index, plus a small number of random reads during the insert phase. This minimizes I/O contention and allows the merge to run in the background with minimal impact on concurrent search operations.

5. Experimental Setup

• Datasets:

  • SIFT1M, GIST1M, DEEP1M: Standard 1-million-point ANNS benchmark datasets with varying dimensions. Used for evaluating FreshVamana.
  • SIFT1B: A very large, 1-billion-point dataset (128 dimensions). A subset of 800 million points was used for the main FreshDiskANN system evaluation, with 200 million held out for insertions.
  • SIFT100M: A 100-million-point subset of SIFT1B.

• Evaluation Metrics:

  • k-recall@k: The primary metric for search accuracy.
    1. Conceptual Definition: It measures the fraction of the true k nearest neighbors that are successfully retrieved by the algorithm within its top k results. For a query q, if the algorithm returns a set of k points X and the true set of k nearest neighbors is G, the recall is the size of the intersection of X and G, divided by k. High recall is desired.
    2. Mathematical Formula: $k\text{-recall}@k = \frac{|X \cap G|}{k}$
    3. Symbol Explanation:
       • $k$: The number of nearest neighbors to retrieve.
       • $q$: The query vector.
       • $P$: The dataset of points.
       • $G \subseteq P$: The set of the actual k nearest neighbors of q in P.
       • $X \subseteq P$: The set of k neighbors returned by the ANNS algorithm for query q.
       • $|\cdot|$: Denotes the number of elements in a set.

• Baselines: The main comparison is not against another streaming algorithm but against the standard industry practice: periodically rebuilding a static index (Vamana for in-memory, DiskANN for SSD). The goal is to show that FreshDiskANN's live updates are far more cost-effective.

6. Results & Analysis

The paper presents a comprehensive set of experiments to validate its claims.

• FreshVamana Recall Stability (Figure 2 & 3):

  • Figure 2 shows that over 50 cycles of deleting and re-inserting 5%, 10%, or even 50% of the data, the recall of FreshVamana remains stable around 95%. This directly contrasts with the degradation seen in Figure 1 for other methods.
  • Figure 3 demonstrates the importance of the α parameter. When $α = 1$ (the strict RNG rule), recall degrades over time. For $α > 1$, recall is stable, confirming that the denser graph structure is key to robustness.

• StreamingMerge Stability (Figure 4):

  • This experiment shows the recall of the SSD-based index over 40 cycles of StreamingMerge. There is an initial drop in recall because the merge process uses approximate distances from compressed vectors. However, after this initial adjustment period (~20 cycles), the recall stabilizes. This proves that the system can maintain a consistent quality of service in a long-running, steady-state scenario.

• Billion-Scale FreshDiskANN Evaluation (Figures 5-8): This week-long experiment on an 800-million-point index is the main result.

  • System Performance: The system sustained a throughput of 1800 inserts/sec and 1800 deletes/sec concurrently with 1000 searches/sec.

  • Search Latency (Figures 5 & 6): User-perceived mean search latency remained low, mostly under 15-20ms, even when a StreamingMerge was active in the background. Latency is lowest when no merge is running (~5ms) and highest during the Insert phase of the merge due to random read contention on the SSD.

  • Update Latency (Figure 6, right): The user-perceived latency for inserts is under 1ms, and for deletes is even lower (microseconds), because they are handled by fast in-memory operations. The system's overall update throughput is limited by the speed of the background StreamingMerge.

  • Cost-Effectiveness (Table 2): The paper shows that merging a 7.5% change (30M inserts + 30M deletes) into an 800M index takes ~16,000 seconds. Rebuilding the entire index from scratch would take ~190,000 seconds. This demonstrates a >10x improvement in efficiency, directly supporting the paper's central claim of a 5-10x cost reduction. The StreamingMerge time also scales near-linearly with the number of threads used (Figure 7).

    Below are manual transcriptions of the tables from the paper.

Table 1: Index build times for Vamana and FreshVamana on mem with $R=64, L_c=75, α=1.2$

This table shows that building an index from scratch by streaming inserts with FreshVamana is ~1.5x faster than the batch-build process of the original Vamana.

Table 2: Full build time with DiskANN (96 threads) versus FreshDiskANN (40 threads) to update a 800M index with 30M inserts and deletes

*Note: The text states a rebuild takes ~190,000 seconds. The 83,140s in the table might refer to a specific configuration or phase. The key takeaway is the order-of-magnitude difference.

7. Conclusion & Reflections

• Conclusion Summary: The paper successfully tackles a critical, practical problem in large-scale ANNS: maintaining index freshness. It introduces FreshVamana, the first graph-based algorithm with robust update rules that preserve search quality. It then engineers FreshDiskANN, a complete system that scales this algorithm to billion-point datasets on a single machine using an efficient StreamingMerge procedure. The system achieves impressive performance, supporting thousands of concurrent updates and queries per second with low latency and high accuracy, all while reducing the cost of maintaining freshness by an order of magnitude compared to the industry-standard practice of periodic rebuilding.

• Limitations & Future Work:

  • Parameter Tuning: The system has several important parameters (α, R, L, merge thresholds) that likely require careful tuning for different datasets and workloads to achieve optimal performance.
  • Consistency Model: The paper assumes quiescent consistency, where a search at time t reflects all updates completed before t. This is a reasonable model but might not be sufficient for applications requiring stricter transactional guarantees.
  • Worst-Case Scenarios: The performance analysis focuses on random updates. A highly skewed or adversarial update pattern (e.g., deleting all the central "hub" nodes in the graph) could potentially degrade performance more significantly.

• Personal Insights & Critique:

  • Impact: This paper is a significant contribution to the field. It makes the best-performing class of ANNS algorithms (graph-based) practical for a much wider range of real-world, dynamic applications. The massive cost reduction it enables is a compelling reason for industry adoption.
  • Engineering Excellence: The design of the StreamingMerge procedure is a standout piece of systems engineering. It elegantly solves the challenge of applying many small, random updates to a massive, disk-resident data structure by converting them into I/O-efficient sequential passes.
  • Future Directions: The principles behind FreshVamana and StreamingMerge could likely be adapted to other graph-based indices beyond Vamana. Furthermore, this work opens the door to building fully-fledged distributed databases for vector search that can handle both high-volume queries and real-time data ingestion efficiently.