软件学报

作者：周依杰，林圣原，巩树凤，余松，范书豪，张岩峰，于戈

单位：周依杰，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081911,林圣原，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081902,巩树凤，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081903,余松，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081904,范书豪，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081905,张岩峰，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081906,于戈，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081907

关键词：高维向量;近似最近邻搜索;索引图

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

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

来源：2026年第3期

《软件学报》期刊编辑部

查看软件学报杂志2026年第3期