In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search

• URL: http://arxiv.org/abs/2502.13826v1
• Date: Wed, 19 Feb 2025 15:41:08 GMT
• Title: In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search
• Authors: Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, Harsha Vardhan Simhadri,
• Abstract summary: IP-DiskANN is first algorithm to avoid batch consolidation by efficiently processing each insertion and deletion in-place. It has stable recall over various lengthy update patterns in both high-recall and low-recall regimes.
• Score: 12.092920351505036
• License:
• 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.

Related papers

• SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search [13.349178274732862]
  We present SymphonyQG, which achieves more symphonious integration of quantization and graph. Based on extensive experiments on real-world datasets, SymphonyQG establishes the new state-of-the-art in terms of the time-accuracy trade-off.
  arXiv  Detail & Related papers  (2024-11-19T04:51:08Z)
• Early Exit Strategies for Approximate k-NN Search in Dense Retrieval [10.48678957367324]
  We build upon state-of-the-art for early exit A-kNN and propose an unsupervised method based on the notion of patience. We show that our techniques improve the A-kNN efficiency with up to 5x speedups while achieving negligible effectiveness losses.
  arXiv  Detail & Related papers  (2024-08-09T10:17:07Z)
• Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation [0.9592510017131104]
  graph-based indices become unacceptable when faced with a large number of real-time deletions, insertions, and updates. We present efficient measures to overcome the shortcomings of HNSW, specifically addressing poor performance over long periods of delete and update operations. Our proposed MN-RU algorithm effectively improves update efficiency and suppresses the growth rate of unreachable points, ensuring better overall performance and maintaining the integrity of the graph.
  arXiv  Detail & Related papers  (2024-07-10T17:37:15Z)
• SOAR: Improved Indexing for Approximate Nearest Neighbor Search [30.752720306189342]
  Spilling with Orthogonality-Amplified Residuals (SOAR) is a novel data indexing technique for approximate nearest neighbor (ANN) search.
  arXiv  Detail & Related papers  (2024-03-31T19:09:09Z)
• On Exploring Node-feature and Graph-structure Diversities for Node Drop Graph Pooling [86.65151066870739]
  Current node drop pooling methods ignore the graph diversity in terms of the node features and the graph structures, thus resulting in suboptimal graph-level representations. We propose a novel plug-and-play score scheme and refer to it as MID, which consists of a textbfMulti score space with two operations, textiti.e., fltextbfIpscore and textbfDropscore. Specifically, the multidimensional score space depicts the significance of nodes through multiple criteria; the flipscore encourages the maintenance of dissimilar node
  arXiv  Detail & Related papers  (2023-06-22T08:02:01Z)
• Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining [61.09807522366773]
  We introduce an algorithm that approximates the softmax with provable bounds and that dynamically maintains the tree. In our study on datasets with over twenty million targets, our approach cuts error by half in relation to oracle brute-force negative mining.
  arXiv  Detail & Related papers  (2023-03-27T15:18:32Z)
• DSI++: Updating Transformer Memory with New Documents [95.70264288158766]
  We introduce DSI++, a continual learning challenge for DSI to incrementally index new documents. We show that continual indexing of new documents leads to considerable forgetting of previously indexed documents. We introduce a generative memory to sample pseudo-queries for documents and supplement them during continual indexing to prevent forgetting for the retrieval task.
  arXiv  Detail & Related papers  (2022-12-19T18:59:34Z)
• End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
  Extreme multi-label classification (XMC) is a popular framework for solving real-world problems. In this paper, we propose a novel method which relaxes the tree-based index to a specialized weighted graph-based index. ELIAS achieves state-of-the-art performance on several large-scale extreme classification benchmarks with millions of labels.
  arXiv  Detail & Related papers  (2022-10-16T01:34:17Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  We propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.
  arXiv  Detail & Related papers  (2022-06-22T22:30:46Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  Autoregressive language models are emerging as the de-facto standard for generating answers. Previous work has explored ways to partition the search space into hierarchical structures. In this work we propose an alternative that doesn't force any structure in the search space: using all ngrams in a passage as its possible identifiers.
  arXiv  Detail & Related papers  (2022-04-22T10:45:01Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.