In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 9 Pith papers
-
Leveraging I/O Stalls for Efficient Scheduling in ANNS
LIOS executes ANNS index updates inside search I/O stall windows via resumable subtasks, overrun bounding, and dynamic fraction adjustment, delivering up to 2.68x insertion and 2.18x deletion speedups in FreshDiskANN ...
-
Decoupling Vector Data and Index Storage for Space Efficiency
DecoupleVS decouples vector data and index storage in ANNS systems to cut storage space by up to 58.7% with competitive search and update performance.
-
Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN
BatANN delivers near-linear throughput scaling for distributed disk-based approximate nearest neighbor search on a single global graph, with 3.5-5.59x gains over scatter-gather baselines on 1B-point datasets at 0.95 recall.
-
Slipstream: Locality-Aware Graph Index Construction for Streaming Approximate Nearest Neighbor Search
Slipstream exploits continuity in vector streams to reduce insertion costs in graph ANNS indexes via prior-insertion candidates and an adaptive controller, delivering up to 30.8x higher throughput at >=0.95 recall@10 ...
-
Onyx: Cost-Efficient Disk-Oblivious ANN Search
Onyx inverts ANN-ORAM optimization priorities with a compact pruning representation and locality-aware shallow tree to deliver 1.7-9.9x lower cost and 2.3-12.3x lower latency for disk-oblivious ANN search.
-
DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries
DGAI decouples vector storage from graph topology in on-disk ANN indexes and adds similarity-aware dynamic layout plus hierarchical PQ two-stage querying to achieve 8x faster insertions/deletions and 67% lower peak qu...
-
NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search
NAVIS improves concurrent search and update throughput in on-SSD graph vector search by up to 2.74x for insertions and 1.37x for searches through reduced position-seeking overhead.
-
Decoupling Vector Data and Index Storage for Space Efficiency
COMPASS decouples vector data and index storage in disk-resident graph ANNS systems to enable component-specific lossless compression, reducing space by up to 58.7% with improved or competitive performance.
-
ScaleGANN: Accelerate Large-Scale ANN Indexing by Cost-effective Cloud GPUs
ScaleGANN accelerates graph-based ANN index construction up to 9x faster and 6x cheaper than DiskANN by using divide-and-merge on distributed low-cost spot GPUs with optimized partitioning and a cost-aware scheduler.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.