CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data
vldb26-3013 · Regular Research · Darae Lee, Min-Soo Kim
Abstract
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.90x higher update throughput.
Assigned reviewers
No reviewers assigned yet.
Candidates from the panel ranked by taxonomy affinity
| # | Reviewer | Match | Load | Why |
|---|