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

周依杰 等: GoVector: I/O-高效的高维向量近邻查询缓存策略 1025

2.5 2.5
Actual (16, 0.31) Actual (8, 0.41)
GoVector (18, 0.36) GoVector (11, 0.59)
2.0 2.0
PANNS (27, 0.39) PANNS (16, 0.51)
距离 (×10 5 ) 1.5 距离 1.5
1.0
1.0
0.5 0.5

0 20 40 60 80 100 0 20 40 60 80 100
拓展轮数 拓展轮数
(a) SIFT (b) GIST
图 3 不同数据集上 ANNS 查询过程中拓展点 p 与查询点 q 的距离变化 (k=10)
∗

第 1 阶段为快速接近查询向量阶段. 多数基于图结构或树结构的 ANNS 算法 (如 HNSW、NSG、KD-Tree [22] )
通常从一组入口顶点开始搜索. 尽管这些入口顶点可能距离查询向量较远, 算法仍可通过图跳跃或树的快速分支
遍历, 在较少跳数内迅速接近查询向量, 此时查询距离迅速下降. 第 2 阶段为 Top-k 结果的精细探索阶段. 此时, 算
法已定位到局部最近邻区域, 但为了获得最终的 Top-k 最优解, 仍需扩展多个邻域分支以排除潜在更优的候选. 该
阶段搜索范围更广, 路径呈现较高的不确定性, 并可能访问到一些距离查询向量更远的候选点, 导致查询距离出现
波动甚至上升的现象.
尽管现有研究已通过向量压缩、路由预测等技术对第 1 阶段进行了优化 [16,23,24] , 但在第 2 阶段, 由于候选扩
展频繁、访问模式分散且数据局部性较差, 传统缓存策略难以有效发挥作用, 频繁的磁盘 I/O 成为制约查询性能
的主要瓶颈. 因此, 本文聚焦于优化查询的第 2 阶段, 通过提升数据局部性与缓存命中率, 有效减少查询过程中的
磁盘访问次数, 提升整体检索效率.

2 研究背景与相关工作

2.1 向量索引
在高维语义向量广泛应用于自然语言处理、推荐系统和图神经网络 [25] 等任务的背景下, 如何设计高效的向
量索引结构, 以支撑大规模、高并发、低延迟的 ANNS, 已成为向量数据库系统的核心挑战. 传统精确检索方式在
高维空间中面临“维度灾难”, 索引构建与查询效率急剧下降, 难以满足在线服务场景的性能需求. 为在检索效率与
精度之间取得平衡, ANNS 索引技术应运而生, 并逐步演化为工业级向量数据库系统 (如 Faiss [26] 和 Milvus [18] ) 的基
础组件. 现有主流的向量索引方法大致可分为如下 3 类.
(1) 哈希索引 (如 LSH [27,28] ): 通过构造多个哈希函数将向量映射至不同的桶 (bucket), 仅在相同桶内执行候选
搜索. 该方法计算开销低, 但在追求高召回率时需构建大量哈希表, 导致内存占用与系统维护成本增加, 扩展性有限.
(2) 量化索引 (如 IVF_PQ [24] 、SCANN [29] ): 对向量空间进行压缩或分区, 以降低计算与存储成本. 此类方法在
工业系统中广泛应用, 如 Faiss 使用乘积量化加速候选聚类定位. 然而, 在高精度检索任务中, 量化误差可能导致相
似向量被映射至不同单元, 降低召回率与整体检索效果.
(3) 索引图 (如 HNSW、NSG、DiskANN): 通过构建稀疏可导航的近邻图, 并结合启发式遍历策略, 实现高维
向量空间中的高效近似搜索. 索引图方法近年来凭借优异的精度与可扩展性, 逐渐成为处理大规模向量检索任务
的主流方案.
2.2 基于索引图的 ANNS 优化技术
索引图方法因其高准确率和良好扩展性受到广泛关注. 其核心思想是: 在构建索引时预计算部分近邻关系, 将
向量作为顶点, 相似度为边, 构建稀疏有向图结构. 查询过程中, 从入口顶点出发, 通过近邻扩展算法实现快速定位