Jul 2026· Proceedings of the VLDB Endowment· Vol 19, pp. 3357-3370· 0 citations· 59 references
Computer Science
TL;DR
This work proposes CONDA, a dynamic graph-based index featuring a topology-aware pruning rule with bidirectional link reinforcement and a lightweight lazy deletion scheme that improves search recall by up to 24.5% over state-of-the-art methods while achieving 1.90× higher update throughput.
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.90× higher update throughput.
Approximate nearest neighbor search (ANNS) underpins large-scale vector retrieval in search, recommendation, and retrieval-augmented generation. Graph-based indexes have demonstrated state-of-the-art search performance for ANNS. They connect each corpus vector to a small set of nearby or navigationally useful vertices...
Bao-Yuan Gu, Xiao-Yao Zhong, Jia-Bao Jin et al.· 0 citations
Graph-based Approximate Nearest Neighbor (ANN) indexes, such as HNSW, are the backbone of modern vector search. However, their massive memory footprint creates a severe infrastructure bottleneck. While vector quantization is widely adopted to reduce the memory required to store data vectors, the graph's edge structure...
Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo et al.· Proceedings of the 35th ACM...· 1 citation
Production vector search must continuously ingest, delete, and re-tenant vectors while serving low-latency, high-recall, metadata-filtered approximate nearest-neighbor (ANN) queries for many tenants with per-tenant service-level objectives. Existing graph-based ANN systems address these requirements largely in isolatio...
Approximate Nearest Neighbor (ANN) search is a foundational primitive in modern recommendation and retrieval systems. However, production deployments routinely require filtered ANN search-retrieving the top- K nearest neighbors that also satisfy metadata predicates-a requirement that popular highperformance libraries s...
Existing approximate nearest neighbor search (ANNS) methods generally assume that each entity has a single vector. In many real-world applications, however, an entity is associated with more than one vector, and queries may jointly consider two attributes. With different queries assigning different weights to each attr...
Sheng-Yuan Lin, Shu-Feng Gong, Zheng Wang et al.· 0 citations
Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm...
