GoVector: I/O-efficient Caching Strategy for High-dimensional Vector Nearest Neighbor Search
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Graph-based indexes for high-dimensional vectors have become the mainstream solution for large-scale approximate nearest neighbor search (ANNS) due to their high efficiency. The search process over graph-based indexes typically consists of two stages: the first stage rapidly navigates from an entry point to a region near the query vector, while the second stage searches for the k nearest vectors within the localized region. However, due to the need to store a large number of adjacency relationships, graph-based indexes often incur high memory overhead. In practice, this leads to storing the index in external memory, where vector and graph data are loaded on demand during ANNS. This results in frequent I/O operations, which have become the primary bottleneck, accounting for over 90% of total query time. Existing systems exploit the fact that entry points and their nearby neighbors are frequently accessed, and adopt static caching strategies that preload these points and their multi-hop neighbors into memory to reduce I/O during the first stage. However, this study finds that the second stage contributes the majority of I/O cost, as it involves accessing a large number of graph vertices related to the query vector to ensure high recall. Since the accessed vertices in this stage vary dynamically with each query, static caching strategies fail to capture them effectively and thus become nearly ineffective. To address this issue, a hybrid caching strategy termed GoVector is proposed, which integrates both static and dynamic components. Specifically, (1) the static cache preloads the entry point and its frequently accessed neighbors, while (2) the dynamic cache adaptively stores high-locality vertices encountered during the second stage of the search. Furthermore, to align with the similarity-driven search behavior of the second stage, a vector-similarity-aware disk layout strategy is proposed, which reorganizes the storage order of vertices to cluster similar vectors into the same or adjacent disk pages, thus enhancing data locality. This dual-optimization approach significantly improves cache hit rates and effectively reduces overall I/O overhead. Experimental results on multiple public datasets demonstrate that, under 90% recall, GoVector achieves an average of 46% fewer I/O operations, 1.73× higher query throughput, and 42% lower latency compared to state-of-the-art disk-based graph indexing ANNS systems.

    Reference
    Related
    Cited by
Get Citation

周依杰,林圣原,巩树凤,余松,范书豪,张岩峰,于戈. GoVector: I/O-高效的高维向量近邻查询缓存策略.软件学报,2026,37(3):1021-1036

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 06,2025
  • Revised:June 30,2025
  • Adopted:
  • Online: September 02,2025
  • Published: March 06,2026
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063