Dynamic index improves dual vector search efficiency and updates
ACTIVE: A Dynamic Pareto-Frontier-Based Unified Index for Dual-Vector Query
Databases
Summary
Searching for matching items becomes complicated when each item has two sets of information, and queries want different balances of these. The authors created ACTIVE, a new way to organize and update this kind of search system more quickly and efficiently. Their method speeds up adding and removing items while keeping search results accurate. Experiments show it works faster than previous methods, especially when making updates.
What this means in practice
- •For recommendation system engineers: Build recommendation engines that efficiently handle items described by two features with varying user preferences for each feature.
- •For geospatial data teams: Improve dynamic searches on spatial data points that have dual attributes like location and time, enabling fast updates and queries.
Authors
Shengyuan Lin, Shufeng Gong, Zheng Wang, Feng Yao, Shifu Li, Yanfeng Zhang, Ge Yu
Abstract
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 attribute, Pareto-frontier-based indices provide an effective solution for dual-vector retrieval by connecting to approximate nearest neighbors under all possible query preferences. However, existing Pareto-frontier-based approaches suffer from substantial inefficiencies in both index construction and dynamic updates, limiting their practical applicability. To address these issues, we propose ACTIVE, a dynamic Pareto-frontier-based DVQ index that supports efficient construction and updates while maintaining high retrieval performance under varying query preferences. It employs angle-constrained active-range computation and connectivity-loss-driven adaptive repair strategies to accelerate node insertion and deletion, respectively. Extensive experiments show that, at comparable (or slightly below) search accuracy, ACTIVE improves insertion throughput by $1.20$--$1.43\times$ over DEG, and deletion throughput by $1.64$--$2.06\times$ over neighbor-reconnection-based repair and by $22.64$--$39.51\times$ over reinsertion-based repair.