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

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

造成该瓶颈的原因主要体现在两个方面. 一方面, ANNS 查询路径具有高度的查询相关性, 其搜索过程依赖于
查询向量在向量空间中的位置, 导致实际访问的顶点在查询发起前难以准确预测. 因此, 当前主流系统普遍采用静
态缓存策略, 即在查询启动前将入口顶点及其若干跳邻居提前加载到内存缓存中, 期望在搜索过程中能够直接命
中这些缓存顶点, 从而减少磁盘读取次数 [11] . 然而, 该策略缺乏对具体查询路径的感知能力, 导致缓存中的大量数
据在实际搜索过程中未被访问, 整体命中率较低. 以 DiskANN 为例, 在进入查询向量邻近区域后, 进行 Top-k 相似
向量搜索时的缓存命中率仅为 4%–9%. 另一方面, 现有系统通常通过索引图的拓扑结构来优化磁盘数据布局, 以
降低 ANNS 查询过程中的 I/O 开销. 例如, Starling [16] 作为当前最先进的磁盘索引图局部性优化方案之一, 通过将
顶点及其拓扑邻居划分至同一磁盘页来减少随机 I/O 操作. 但该方法忽略了基于索引图查询的特殊性, 即查询过
程中拓展节点的选择并非严格遵循拓扑结构的广度或深度优先顺序, 而是根据与查询点的距离来决定候选扩展顶点.
综上所述, 本文总结了当前基于磁盘的索引图方法在降低 I/O 开销方面面临的两大挑战.
(1) 缓存命中率低. 由于查询路径具有查询相关性与动态性, 现有静态缓存策略无法感知查询路径, 难以准确
命中查询路径中的顶点. 需设计一种灵活且查询自适应的缓存机制, 能够根据查询向量的特性, 有选择性地缓存在
搜索过程中可能被访问的关键顶点, 从而提高缓存命中率, 减少不必要的磁盘访问.
(2) 单次 I/O 的数据利用率不足. 现有以图拓扑为基础的索引布局方式, 无法充分反映实际查询路径中的访问
规律, 导致每轮磁盘加载中仅有少部分数据被有效利用. 因此, 需结合 ANNS 的搜索特性, 重新设计索引的物理组
织方式, 提升索引图访问的局部性, 使单次 I/O 能加载更多与当前查询相关的向量和邻接信息, 从而提升整体检索
性能.
针对上述两项挑战, 本文提出 GoVector, 一种 I/O 高效的基于磁盘索引图的高维向量近邻查询缓存策略, 旨在
通过查询感知的混合缓存和基于向量相似性的索引图重排策略来提升基于磁盘的索引图系统的查询效率. 本文的
主要贡献如下.
(1) 提出了一种静态-动态混合缓存策略. 其中, 静态部分用于预加载入口顶点及其若干跳邻居, 以快速定位至
查询向量所在的近邻区域; 动态部分用于自适应地缓存查询路径上的候选顶点及其在向量空间中相似的邻近顶
点, 以提升相似向量搜索阶段的缓存命中率.
(2) 设计了一种基于向量相似性的索引布局优化策略, 通过将相似度高的向量集中存储在同一或相邻的磁盘
页中, 提升了单次 I/O 中的有效数据量, 从而减少 I/O 次数, 优化整体磁盘访问性能.
(3) 在多个公开数据集上开展了系统性评估, 结果表明: 与现有方法相比, GoVector 将 I/O 次数平均减少 46%
(最高 57%), 查询吞吐率提升 1.73 倍 (最高 2.25 倍), 查询延迟降低 42% (最多 55%).
本文第 1 节介绍基础知识. 第 2 节介绍研究背景与相关工作. 第 3 节介绍 GoVector 的方法概览与系统架构.
第 4、5 节介绍 GoVector 的核心设计: 混合缓存机制与索引图重排序. 第 6 节给出实验设置与性能评估结果. 第 7
节对全文进行总结.

1 基础知识

1.1 ANNS 问题定义
近似最近邻搜索 [10,19,20] 的目标是在一个高维向量集合中, 快速找到与给定查询向量最相似的 Top-k 向量 [16] .
给定一个包含 n 个高维向量的数据集 V = {v 1 ,v 2 ,...,v n } ⊂ R , 以及一个查询向量 q ∈ R , ANNS 的目标是在 V 中找
d
d
到与 q 距离最近的 k 个向量, 即返回集合:

∑
Top-k(q) = argmin d(q,v),
R⊆V,|R|=k
v∈R
其中, d(·,·) 表示向量空间中的距离函数, 常用的包括欧几里得距离、余弦相似度等; R 表示候选的 Top-k 查询结
果集合.
召回率 (Recall) 是衡量向量检索质量的核心指标之一, 用于评估搜索返回结果中包含多少真实的最近邻. 设