Page 58 - 《软件学报》2026年第3期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(3):1021−1036 [doi: 10.13328/j.cnki.jos.007518] [CSTR: 32375.14.jos.007518] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
GoVector: I/O-高效的高维向量近邻查询缓存策略

周依杰, 林圣原, 巩树凤, 余 松, 范书豪, 张岩峰, 于 戈

(东北大学 计算机科学与工程学院, 辽宁 沈阳 110819)
通信作者: 巩树凤, E-mail: gongsf@mail.neu.edu.cn

摘 要: 基于图结构的高维向量索引 (索引图) 因其高效的近似最近邻搜索能力, 已成为大规模向量检索的主流方
法. 索引图执行近似最近邻搜索 (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%.
关键词: 高维向量; 近似最近邻搜索; 索引图
中图法分类号: TP311

中文引用格式: 周依杰, 林圣原, 巩树凤, 余松, 范书豪, 张岩峰, 于戈. GoVector: I/O-高效的高维向量近邻查询缓存策略. 软件学
报, 2026, 37(3): 1021–1036. http://www.jos.org.cn/1000-9825/7518.htm
英文引用格式: Zhou YJ, Lin SY, Gong SF, Yu S, Fan SH, Zhang YF, Yu G. GoVector: I/O-efficient Caching Strategy for High-
dimensional Vector Nearest Neighbor Search. Ruan Jian Xue Bao/Journal of Software, 2026, 37(3): 1021–1036 (in Chinese). http://
www.jos.org.cn/1000-9825/7518.htm

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

ZHOU Yi-Jie, LIN Sheng-Yuan, GONG Shu-Feng, YU Song, FAN Shu-Hao, ZHANG Yan-Feng, YU Ge
(School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China)
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

* 基金项目: 国家自然科学基金 (U2241212, 62461146205); 国家社会科学基金 (21&ZD124); 中央高校基本科研业务费专项资金
(N2116005, N2116008, N2416003); CCF-华为胡杨林基金
周依杰和林圣原为共同第一作者.
本文由“向量数据库及 DB4LLM 技术”专题特约编辑高宏教授、李国良教授、张蓉教授推荐.
收稿时间: 2025-05-06; 修改时间: 2025-06-30; 采用时间: 2025-08-20; jos 在线出版时间: 2025-09-02
CNKI 网络首发时间: 2026-01-15