Graph-based indexes have become the dominant approach to approximate nearest neighbor search (ANNS) over high-dimensional data and play a crucial role in real-world applications such as retrieval-augmented generation, recommendation systems, and vector databases. Despite extensive progress in static graph construction and search, efficient in-place deletion remains challenging because obsolete vectors must be removed without allowing stale incoming edges to consume search capacity or expensive graph-wide maintenance to interrupt online services, e.g., retrieval-augmented generation (RAG) and recommendation platforms. To address this problem, we propose MERIT (MST-based Efficient Repair with In-place updaTes), an in-place update framework with three core techniques: (1) bounded search-based recovery that combines a deleted vertex's outgoing neighbors with its readily searchable in-neighbors, (2) $k_r$-Minimum Spanning Tree (MST) local repair that promotes local connectivity while retaining multiple routing choices for graph search, and (3) versioned-edge invalidation that immediately filters all stale incoming edges to the deleted vertex and progressively removes them as adjacency lists are rewritten. Its integration with the hierarchical HNSW index and the single-layer Vamana index demonstrates applicability across distinct graph structures. Extensive experiments on multiple real-world datasets show that MERIT processes deletion at nearly the cost of inserting one vector, achieves up to $3.02\times$--$18.87\times$ faster deletion than state-of-the-art (SOTA) methods, and keeps search recall stable or even improves it as deletions accumulate.
Approximate Nearest Neighbor (ANN) search is a core operation in large-scale vector databases that support recommendation, semantic search, and retrieval-augmented generation. Graph-based indexes are widely used for their superior search performance at million scale, but scaling them to billion-scale datasets exposes a fundamental trade-off between construction efficiency and search performance. CPU-based methods produce high-quality graphs enabling fast search but require multiple days to construct, while GPU-based methods accelerate construction at the cost of degraded search performance. This trade-off stems from the traditional requirement of enforcing global connectivity during graph construction. We observe that graph-based search primarily depends on local connectivity between entry points and a query's nearest neighbors, making global connectivity unnecessary for high search performance. In this paper, we introduce HEXA, a disjoint-subgraph-based indexing framework that partitions the dataset into disjoint clusters and constructs refined proximity subgraphs independently on GPUs. At query time, HEXA employs a two-level routing structure to select relevant subgraphs and query-close entry points, then applies a budget-adaptive search algorithm that allocates exploration effort based on each subgraph's likelihood of containing nearest neighbors. Experiments on billion-scale datasets demonstrate that HEXA achieves up to 14.7 times higher query throughput at the same recall levels compared with various indexing methods, and reduces construction time to approximately one hour.
Yi-Fei Xu, Yan-Yan Shen, Youmin Chen et al.· Proceedings of the VLDB Endo...· 0 citations
PIGR (Post-hoc Iterative Graph Refinement), a trace-driven framework that explicitly aligns efficiency with observed search behavior, is introduced, which delivers 1.3x-2.5x speedups at near-exact recall across diverse datasets and index families, consistently outperforming the best build-time tuned baselines.
Zhiwei Zhang, Weiguo Zheng· Proceedings of the 32nd ACM...· 0 citations
GrAND (GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search) is presented, a GPU-native collection of dynamic-update algorithms for two popular graph indexes, Vamana and CAGRA, that improves overall workload throughput and maintains high search throughput and recall over sustained updates.
Karthik Venkatasubba, Shivendra Deshpande, S. Shivram et al.· 0 citations
Graph-based Approximate Nearest Neighbor Search (ANNS) indices must support continuous vector updates while maintaining both high search performance and low update overhead for real-world applications such as RAG systems and streaming services. Existing in-place update methods often lose search accuracy due to graph connectivity loss and suffer high overhead from expensive deletion operations. We propose CONDA, a dynamic graph-based index featuring a topology-aware pruning rule with bidirectional link reinforcement and a lightweight lazy deletion scheme. Extensive experiments demonstrate that CONDA improves search recall by up to 24.5% over state-of-the-art methods while achieving 1.90× higher update throughput.
Darae Lee, Min-Soo Kim· Proceedings of the VLDB Endo...· 0 citations
Filtered Approximate Nearest Neighbor Search (FANNS) augments vector retrieval with categorical label predicates and is now standard in vector databases. Existing label-integrated graph indices, however, lose substantial recall on queries whose label is rare—the long-tail regime that dominates real workloads. We trace this failure to construction: distance-greedy neighbor selection and pruning systematically under-allocate edges to low-frequency labels, leaving their subgraphs poorly connected. Meanwhile, high-frequency labels accumulate redundant edges—slack that can be reallocated with limited impact on their search quality. Building on this insight, we propose LBGraph, which replaces both construction phases with label-balanced counterparts: a per-label round-robin candidate pool during exploration, and a label-then-distance rule during pruning. On low-frequency-label queries, LBGraph raises recall@10 by up to 71 percentage points (from 20% to 91%) over FilteredVamana on synthetic-label SIFT1M and GIST, with smaller gains on real-label LAION1M. Against ACORN-γ and StitchedVamana, it achieves up to 4 × their QPS at 90% recall@10 on low-frequency-label workloads while staying competitive on mixed workloads.
Hanchao Zheng, Yang Chen, Zhe Wu· International Conference on...· 0 citations
We present TiGER (Time-Integrated Graph for Efficient Retrieval), a novel approach for performing fast time-aware approximate nearest neighbor searches on dynamic vector datasets with flexibility over any possible time range. Our proposed algorithm builds and maintains a unified graph for all vectors by leveraging an index structure based on integrated versioned connectivity, allowing arbitrary time intervals to be queried directly on the unified graph without having to traverse invalid vectors. This forgoes the need for post-search filtering or merging, or separate graphs for each possible composite range. Empirical evaluations show that our method attains up to a 5x improvement in queries per second (QPS) without compromising accuracy over baselines based on filtering or per-time-segment sub-graphs. We believe that this method will enable efficient temporal analysis across evolving datasets in real-time recommendation systems, log analysis, and any scenario requiring fast similarity search over dynamic, time-segmented data.
Jun Woo Chung, Weijie Zhao· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
