Accelerating High-Dimensional Nearest Neighbor Search with Dynamic Query Preference

Abstract

Approximate Nearest Neighbor Search (ANNS) is a crucial operation in databases and artificial intelligence. While graph-based ANNS methods like HNSW and NSG excel in performance, they assume uniform query distribution. However, in real-world scenarios, user preferences and temporal dynamics often result in certain data points being queried more frequently than others, and these query patterns can change over time. To better leverage such characteristics, we propose DQF, a novel Dual-Index Query Framework. This framework features a dual-layer index structure and a dynamic search strategy based on a decision tree. The dual-layer index includes a hot index for high-frequency nodes and a full index covering the entire dataset, allowing for the separate management of hot and cold queries. Furthermore, we propose a dynamic search strategy that employs a decision tree to determine whether a query is of the high-frequency type, avoiding unnecessary searches in the full index through early termination. Additionally, to address fluctuations in query frequency, we design an update mechanism to manage the hot index. New high-frequency nodes will be inserted into the hot index, which is periodically rebuilt when its size exceeds a predefined threshold, removing outdated low-frequency nodes. Experiments on four real-world datasets demonstrate that the Dual-Index Query Framework achieves a significant speedup of 2.0-5.7x over state-of-the-art algorithms while maintaining a 95% recall rate. Importantly, it avoids full index reconstruction even as query distributions change, underscoring its efficiency and practicality in dynamic query distribution scenarios.

The Challenge of Uniformity

Approximate Nearest Neighbor Search (ANNS) is the backbone of modern AI, powering everything from Retrieval-Augmented Generation (RAG) to recommendation engines. Current gold-standard algorithms, such as Hierarchical Navigable Small World (HNSW), are incredibly fast. However, they possess a significant blind spot: they treat every vector in the database with equal priority.

Expand

Source, p. 2

In reality, user preferences are rarely uniform. They typically follow a "long tail" or Zipf’s Law distribution, where a small subset of "hot" items receives the vast majority of search traffic. For example, a trending video or a breaking news story creates a localized cluster of high-frequency queries. Furthermore, these preferences are dynamic—what is popular today may be irrelevant tomorrow. Existing graph-based indices are expensive to build; attempting to "re-weight" a massive graph every time query patterns shift would result in more time spent on index reconstruction than on actual searching.

The Dual-Index Query Framework (DQF)

To address these challenges, the Dual-Index Query Framework (DQF) introduces a structural approach to prioritizing "hot" data without sacrificing the ability to find "cold" data. The framework is built upon three main pillars:

1. Dual-Layer Index Structure

Instead of a single monolithic graph, DQF maintains a Hot Index containing only high-frequency nodes and a Full Index encompassing the entire dataset. Because graph search complexity is logarithmic relative to the number of nodes, searching a compact Hot Index is significantly faster than traversing the full dataset.

Expand

Source, p. 2

2. Dynamic Search with Decision Trees

The "brain" of DQF is a machine-learning-based decision tree that manages search routing. When a query is initiated, the system first probes the Hot Index. As it transitions to the Full Index, the decision tree monitors real-time search features, such as the number of distance calculations performed and the frequency of result updates. If the model predicts that the Full Index is unlikely to yield better results than those already retrieved from the Hot Index, it triggers an early termination. This effectively "skips" the heavy lifting for high-frequency queries, which constitute the majority of the workload.

3. Flexible Update Mechanism

To handle "query shift," DQF tracks query counts for every node. When new nodes gain popularity, they are incrementally inserted into the small Hot Index. To prevent the Hot Index from becoming cluttered with outdated data, it is periodically rebuilt—a process hundreds of times faster than rebuilding the Full Index.

Performance and Adaptability

The framework was evaluated on four high-dimensional benchmarks: SIFT1M, GIST1M, Crawl, and GloVe. To simulate real-world conditions, researchers applied a Zipf distribution ($g(x) = 1/x^\beta$ with $\beta = 1.2$) to the query patterns.

DQF achieved a 2.0× to 5.7× increase in Queries Per Second (QPS) compared to state-of-the-art methods like HNSW and NSG, while maintaining a 95% recall rate. Notably, the Hot Index is extremely memory-efficient; for a 1-million-point dataset, it adds only about 1MB of overhead.

While performance was slightly less pronounced on the GloVe dataset due to its high vector density, the framework demonstrated remarkable resilience to shifting query distributions. By avoiding full index reconstruction, DQF proves to be a practical and efficient solution for dynamic, real-world search environments.

Conclusion

DQF represents a shift from static, uniform indexing to a dynamic, preference-aware approach. By treating the Hot Index as a structural "cache" for similarity searches, and using decision trees to optimize search paths, DQF provides a scalable path forward for high-performance vector databases. Future work will explore more sophisticated routing models and the application of this dual-index approach to disk-based storage systems.

@misc{gao2025accelerating,
  author = {Yunjun Gao and Ruijie Zhao and Zhonggen Li and Baihua Zheng and Yifan Zhu and Zhaoqing Chen},
  title = {{Accelerating High-Dimensional Nearest Neighbor Search with Dynamic Query Preference}},
  year = {2025},
  eprint = {2508.07218},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.07218},
}