Accelerating High-Dimensional Nearest Neighbor Search with Dynamic Query Preference

Approximate Nearest Neighbor Search (ANNS) has emerged as an essential operation in modern database and AI systems. While graph-based methods like NSG demonstrate state-of-the-art ANNS performance, they typically ignore that query distributions are often skewed. In real-world scenarios, user preferences and time-varying access patterns lead to non-uniform workloads, where specific data regions are retrieved significantly more frequently than others. Meanwhile, these patterns evolve over time, making pre-built indexes outdated and thus inefficient for future query workloads. Motivated by this, we propose DQF, a novel Dual-Index Query Framework for dynamic query preference. This dual-index structure comprises a Hot Index containing frequently accessed nodes and a Full Index covering the entire dataset, so that hot queries can be answered faster within the compact Hot Index while cold queries still obtain complete results from the Full Index. Furthermore, we propose a three-phase competitive search in which both layers share a single priority queue. A lightweight decision tree detects when the top-k results have stabilized and triggers per-query early termination. To address temporal shifts in query patterns, we design an adaptive update mechanism that periodically promotes new high-frequency nodes to the Hot Index while demoting outdated ones. Experiments on five real-world datasets demonstrate that DQF achieves a 2.2-6.9x speedup over the strongest baseline on each million-scale dataset at 95% recall. Moreover, it scales to 100M vectors with consistent performance gains, successfully adapting to distribution shifts without requiring Full Index reconstruction.