REVIEW 6 cited by
In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
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.
Forward citations
Cited by 6 Pith papers
-
Efficient and Effective In-place Graph-based Vector Index Updates
Yi introduces a vector-level update mechanism plus a tasklet engine, asynchronous buffer manager, and vector file system for in-place graph-based vector index updates, outperforming OdinANN in throughput, search QPS, ...
-
ETALE: Evolving Topology with Accelerated Lock-free Execution for Dynamic Graph ANN Search on GPUs
A lock-free copy-on-write slab graph on GPUs supports streaming ANN insert/delete with proven deletion monotonicity, bounded VRAM, and 4.8–8.8× faster maintenance than CAGRA rebuilds at recall >0.95.
-
CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search
CleANN combines workload-aware bridge building, on-the-fly neighborhood consolidation, and semi-lazy memory cleaning to keep graph-based ANNS recall near static-build levels under fully dynamic concurrent workloads.
-
MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes
MERIT makes vector-graph deletions cheap by repairing only a bounded local neighborhood via k_r-MST and invalidating all leftover stale edges with per-target version stamps.
-
Beyond Storage: State as a Runtime Control Problem in Parallel and Distributed Systems
State management across streaming, serving, retrieval, and learning systems is best modeled as one coupled runtime control loop spanning access, execution, and evolution.
-
Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
A distance-based stopping rule for beam search in graph-based ANN is proven to give exact or approximate nearest neighbors on navigable graphs and beats fixed-width beam search in experiments.
Discussion (0). Continue with ORCID to comment.