GoVector: I/O-高效的高维向量近邻查询缓存策略
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金 (U2241212, 62461146205); 国家社会科学基金 (21&ZD124); 中央高校基本科研业务费专项资金 (N2116005, N2116008, N2416003); CCF-华为胡杨林基金


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    基于图结构的高维向量索引 (索引图)因其高效的近似最近邻搜索能力, 已成为大规模向量检索的主流方法. 索引图执行近似最近邻搜索 (approximate nearest neighbor search, ANNS)的过程分为两个阶段: 第1阶段从入口点出发快速定位到查询向量附近区域; 第2阶段在查询向量附近搜索离其最近的k个向量. 然而, 由于索引图需存储大量邻接关系, 导致内存开销大, 因此实际部署时通常需将其存储于外存. 当执行近似最近邻搜索时, 按需加载索引图和向量数据会导致频繁发生I/O操作, 并成为检索性能的主要瓶颈 (I/O时间占90%以上). 现有系统利用入口点及其附近邻居被高频访问的特性, 采用静态缓存策略将入口点及其若干跳邻居预先缓存在内存中, 以减少第1阶段的I/O访问. 然而分析发现, 第2阶段为了获取更高精度的检索结果, 需访问大量与查询向量相关的图顶点, 成为I/O开销的主要来源. 由于第2阶段的访问顶点随查询向量动态变化, 现有静态缓存策略难以有效命中, 导致其在此阶段几乎失效. 针对此问题, 设计了一个静态-动态混合缓存策略GoVector, 其核心设计体现在: (1) 静态缓存区预加载入口点及其高频近邻; (2) 动态缓存区自适应地缓存第2阶段中空间局部性高的顶点. 为了进一步适配第2阶段中以向量相似性为导向的搜索过程, 设计了基于向量空间相似性磁盘布局策略, 通过重排顶点存储顺序, 使相似向量在物理存储上聚集于相同或相邻磁盘页, 从而显著提升数据访问的局部性. 这种双重优化机制使得缓存命中率得到显著提升, 有效降低了整体I/O开销. 在多个公开数据集上的实验结果表明, 当召回率为90%时, 相较于当前最先进的基于磁盘的索引图系统, GoVector实现I/O次数平均降低46%、查询吞吐率提升1.73倍、延迟下降42%.

    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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-05-06
  • 最后修改日期:2025-06-30
  • 录用日期:
  • 在线发布日期: 2025-09-02
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号