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

#ReviewerMatchLoadWhy