Source-linked AI summary
In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search
Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, Harsha Vardhan Simhadri
TL;DR
Streaming vector indexes need to absorb updates while maintaining quality, but updating proximity graphs is difficult. IP-DiskANN processes DiskANN deletions in-place to avoid periodic batch consolidation. The authors report stable recall across update patterns and better query and update complexity than previous graph-based indices.
Problem
Streaming vector indexes must incorporate updates while maintaining query quality, but handling graph-index deletions and replacements is challenging.
Source: §1 · pp. 1–2Method
IP-DiskANN handles deletions in a DiskANN graph in-place, avoiding periodic batch consolidation or rebuilds.
Source: §1 · p. 2Results
IP-DiskANN has stable recall across varied update patterns and better query and update complexity than previous graph-based indices.
Source: §7 · p. 10Takeaways & Limitations
Avoiding periodic consolidation avoids the usage spikes and query inefficiencies associated with approaches that consolidate updates into the primary index.
Source: §7 · p. 10Deletion handling is not perfectly online because the algorithm periodically scans the index to remove dangling edges.
Source: §3.3 · p. 4
Abstract
from arXiv · showhide
Indices for approximate nearest neighbor search (ANNS) are a basic component for information retrieval and widely used in database, search, recommendation and RAG systems. In these scenarios, documents or other objects are inserted into and deleted from the working set at a high rate, requiring a stream of updates to the vector index. Algorithms based on proximity graph indices are the most efficient indices for ANNS, winning many benchmark competitions. However, it is challenging to update such graph index at a high rate, while supporting stable recall after many updates. Since the graph is singly-linked, deletions are hard because there is no fast way to find in-neighbors of a deleted vertex. Therefore, to update the graph, state-of-the-art algorithms such as FreshDiskANN accumulate deletions in a batch and periodically consolidate, removing edges to deleted vertices and modifying the graph to ensure recall stability. In this paper, we present IP-DiskANN (InPlaceUpdate-DiskANN), the first algorithm to avoid batch consolidation by efficiently processing each insertion and deletion in-place. Our experiments using standard benchmarks show that IP-DiskANN has stable recall over various lengthy update patterns in both high-recall and low-recall regimes. Further, its query throughput and update speed are better than using the batch consolidation algorithm and HNSW.
1 Introduction
ANNS serves information retrieval and online applications, while continuously changing vector collections make streaming index updates necessary. This section motivates in-place graph updates and introduces IP-DiskANN as an alternative to periodic consolidation.
1 Introduction
- Proximity graphs offer practical trade-offs among accuracy, latency, and throughput, but supporting streaming updates while preserving query quality remains challenging.Insertions are comparatively straightforward, whereas deletions and replacements complicate quality maintenance.Source: §1 · pp. 1–2
- FreshDiskANN incrementally merges tiered segments, but periodic merges still create query-latency and resource spikes and require queries across multiple segments.Tombstone-based deletion can degrade query quality over time, while segment-based strategies also periodically merge or rebuild indices.Source: §1 · p. 2
- The desired in-place update method should be fast, preserve high recall over long periods, and avoid rebuild-related resource and query-latency spikes.A single graph absorbing streaming updates is the proposed way to avoid periodic rebuild spikes and support a stable, low-cost online service.Source: §1 · p. 2
- Because the graph is singly linked, deleting a vertex leaves its in-neighbors unknown; storing them would halve graph capacity or double cost and increase locking complexity.The paper therefore treats maintaining in-neighbors as unacceptable in practice.Source: §1 · p. 2
- IP-DiskANN avoids periodic batch consolidation or rebuilds while maintaining stable recall and improving query and update performance against prior graph-based approaches.The paper reports query efficiency comparable to a graph built from scratch, lower update cost than static construction and lazy approaches, and lower update cost than HNSW with comparable or better recall.Source: §1 · p. 2
2 Preliminaries and Notation
The preliminaries define the streaming point-set operations and notation used to describe index quality and graph structure. They evaluate query answering through recall and query complexity, alongside insertion and deletion costs.
2 Preliminaries and Notation
- The streaming problem operates on a time-varying point set P_t and supports point insertion, deletion, and nearest-neighbor search.Points and vertices are used interchangeably, and the maximum number of out-neighbors is denoted R.Source: §2 · p. 2
- Recall@k measures the overlap between the actual k nearest points and the k vectors returned by an approximate-neighbor algorithm.The paper reports recall@10 as its standard practice.Source: §2 · p. 2
- Index performance is assessed by the recall–query-complexity trade-off and the complexity of handling insertions and deletions.Query complexity may be represented by latency, throughput, or the number of indexed points compared; graph notation uses G(P_t, E_t), N_out(p), and N_in(p).Source: §2 · p. 2
3 Algorithms
This section reviews DiskANN’s search and insertion procedures, FreshDiskANN’s batch consolidation for deletions, and IP-DiskANN’s in-place alternative. IP-DiskANN approximates a deleted vertex’s in-neighbors, adds replacement edges, and periodically removes remaining dangling edges.
3 Algorithms
- The section introduces DiskANN and FreshDiskANN as baselines before presenting IP-DiskANN’s in-place deletion algorithm.The review covers searching, incremental indexing, and consolidation.Source: §3 · p. 3
3.1 DiskANN
- GreedySearch explores the closest unexplored vertex, adds its out-neighbors to a distance-ordered priority queue, and returns the top-k vertices seen.Search begins at a fixed starting point and continues until the top-l_s vertices in the queue have been explored.Source: §3.1 · p. 3
- DiskANN inserts a vector by searching for it, pruning the visited vertices to at most R candidates, connecting them bidirectionally, and pruning any over-degree neighborhoods.RobustPrune retains nearby and directionally diverse distant nodes; its parameter α is typically 1.2.Source: §3.1 · p. 3
3.2 FreshDiskANN
- FreshDiskANN marks deleted vertices online but periodically consolidates the graph, bypassing the need to maintain in-neighbors explicitly.Consolidation redirects upstream neighbors toward downstream neighbors of deleted vertices and prunes neighborhoods that exceed the degree limit.Source: §3.2 · p. 3
3.3 In-place deletion algorithm
- Because practical implementations do not explicitly store in-neighbors, IP-DiskANN reruns GreedySearch and treats visited nodes with an edge to the deleted point as an approximation of its in-neighbors.The approach relies on the expectation that the new visited list approximates the list from the point’s insertion.Source: §3.3 · p. 4
- IP-DiskANN replaces edges around a deleted vertex with locally selected alternatives, then applies RobustPrune when updated vertices exceed the degree bound.For each in-neighbor approximation, it selects candidates close to both the deleted vertex and endpoint; replacement edges for out-neighbors are selected similarly.Source: §3.3 · p. 4
- Dangling edges to a deleted vertex may remain, so IP-DiskANN periodically scans the index to remove them without distance calculations.The scan is usually triggered after deletions exceed a chosen fraction of the index size; the authors describe it as lightweight, but the deletion algorithm is not perfectly online.Source: §3.3 · p. 4
4 Experiments
The experiments evaluate IP-DiskANN across streaming runbooks, recall regimes, and index sizes. Across the reported comparisons, it maintains or improves recall while using fewer distance computations and offering faster queries than FreshDiskANN.
4 Experiments
- Runbooks vary update timing and deletion locality; the experiments include sliding-window, mixed-lifetime, and clustered patterns, with high- and low-recall parameter settings.The clustered pattern inserts and deletes nearby vectors together; the experiments also scale Wiki expiration-time runbooks from 1 to 10 to 35 million points.Source: §4 · pp. 4–5, §4.1 · p. 7
4.1 Observations
- For datasets above 10 million points, IP-DiskANN handled deletions faster than FreshDiskANN and HNSW, while average insertion and search times were roughly similar.HNSW’s deletion time is counted as insertion time because deletion uses replacement.Source: §4.1 · p. 5, Table 1 · p. 5, §4 · p. 5
- On MSTuring-30M-Clustered snapshots, rebuilding from scratch did not achieve optimal recall even relative to FreshDiskANN.The authors hypothesize that evolving edges improve connectivity and traversal over the initial graph.Source: Figure 2 · p. 7, §4.1 · p. 7
- At 1 million points IP-DiskANN deletion took longer, but it became considerably faster at 10 million and beyond as its search for alternative edges scaled sublinearly.FreshDiskANN scans the index to clean adjacency lists, a process described as scaling linearly with data size.Source: §4.1 · p. 7
5 Ablation studies
The ablations show that deletion recall improves with larger candidate lists, more replacement edges, and wider search beams, while these settings increase deletion cost. More frequent lightweight consolidation also raises recall, with a slight deletion-time increase.
5 Ablation studies
- Recall increases gradually with l_d but stops increasing at 200, where the higher maintenance cost outweighs the marginal recall gain.The evaluated l_d values are 60, 128, and 200.Source: §5 · p. 8, Figure 3 · p. 8
- More frequent consolidation raises average recall because fewer dangling edges make greedy search less likely to reach dead ends, while slightly increasing deletion time.Figure 4 varies threshold t; Table 4 reports Recall@10 and total deletion time for those thresholds.Source: §5 · p. 8, Figure 4 · p. 8, Table 4 · p. 8
6 Related Work
Related work spans several vector-index structures, but the paper concentrates on proximity graphs and streaming updates to them. Existing alternatives include partition-based methods, LSH, and prior graph-update approaches, each with stated scope or trade-offs.
6 Related Work
- The paper reports higher, stable FreshDiskANN recall than SPFresh on the discussed runbooks, but leaves normalized-workload comparisons with IVF and LSH methods for future work.It also notes that Ada-IVF’s clustered-runbook results do not compare against other algorithms in the NeurIPS’23 BigANN track [39].Source: §6 · p. 9
- LSH has theoretical accuracy–query-complexity trade-offs, but the paper describes high memory use and weaker performance on disk-resident data; Parallel LSH handles updates through a periodically merged delta table.The paper says graph methods achieve scale and query throughput with fewer machines than PLSH.Source: §6 · p. 9
- Proximity graphs use greedy search and differ chiefly in graph construction; the paper focuses on DiskANN and notes possible extension of its algorithm to other graph indices.The authors cite DiskANN’s benchmark performance, in-memory and on-disk operation, and commercial use as reasons for that focus.Source: §6 · pp. 9–10
- The cited prior in-place DiskANN deletion method [55] stores pointers to in-neighbors, which the paper identifies as expensive; it replaces deleted-vertex edges with diverse neighbors.Its experiments report faster queries at a given recall goal than other heuristics and often a fresh graph rebuild.Source: §6 · p. 10
7 Conclusion
The conclusion presents IP-DiskANN as an in-place deletion algorithm for singly-linked DiskANN graphs, with stable recall across update patterns and improved query and update complexity versus prior graph-based indices. The authors identify adversarial replacement workloads and comparisons with streaming methods for other data structures as future work.
7 Conclusion
- IP-DiskANN is presented as the first in-place deletion algorithm for DiskANN’s common singly-linked proximity graph, with stable recall across varied update patterns and better query and update complexity than prior graph-based indices.It avoids usage spikes and query inefficiencies associated with periodically consolidating delta-file updates.Source: §7 · p. 10
- Future work includes testing other adversarial workloads, such as replacements, and comparing IP-DiskANN with leading streaming methods for IVF and LSH.Source: §7 · p. 10