In-place Updates Of A Graph Index For Streaming Approximate Nearest Neighbor Search

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyxu2025in

Related papers

• Freshdiskann: A Fast And Accurate Graph-based ANN Index For Streaming Similarity Search (2021)0.00
• DGAI: Decoupled On-disk Graph-based ANN Index For Efficient Updates And Queries (2025)0.00
• Diskann++: Efficient Page-based Search Over Isomorphic Mapped Graph Index Using Query-sensitivity Entry Vertex (2023)0.00
• Ood-diskann: Efficient And Scalable Graph ANNS For Out-of-distribution Queries (2022)0.00
• Enhancing HNSW Index For Real-time Updates: Addressing Unreachable Points And Performance Degradation (2024)1.56
• BAMG: A Block-aware Monotonic Graph Index For Disk-based Approximate Nearest Neighbor Search (2025)0.00
• SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (2021)0.00
• Aisaq: All-in-storage ANNS With Product Quantization For Dram-free Information Retrieval (2024)0.00