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

作者简介:

通讯作者:

中图分类号:

TP311

基金项目:

国家自然科学基金(U2241212,62461146205);国家社会科学基金(21&ZD124);中央高校基本科研业务费(N2116005,N2116008,N2416003);辽宁省杰青基金(2024021148-JH3/501);CCF-华为胡杨林基金


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

Fund Project:

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

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

    Abstract:

    Graph-based index for high-dimensional vectors has become the mainstream solution for large-scale approximate nearest neighbor search (ANNS) due to its high efficiency. The search process over graph-based index 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 on 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, our analysis shows 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 points in this stage varies dynamically with each query, static caching strategy fails to capture it effectively and thus becomes nearly ineffective. To address this issue, we propose GoVector, a hybrid caching strategy that 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 phase, we propose a vector-similarity-aware disk layout strategy that reorganizes the storage order of vertices, clustering similar vectors into the same or adjacent disk pages to enhance data locality. This dual-optimization approach greatly enhances cache hit rates and effectively reduces overall I/O overhead. Experiments on multiple public datasets demonstrate that 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 under 90% recall.

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

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

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • 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号