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

1024 软件学报 2026 年第 37 卷第 3 期

ANN k (q), 则 Top-k 召回率定义为:
数据集中与 q 的真实最近邻集合为 GT k (q), 系统返回的近似结果集合为

|ANN k (q)∩GT k (q)|
Recall@k(q) = .
k
Recall 的取值范围为 [0, 1], 数值越接近 1 表示结果越准确. ANNS 的目标是在尽可能保证召回率的前提下,
降低查询延迟与资源消耗 (如内存与 I/O 次数), 从而在大规模高维数据场景中实现可扩展的高效向量检索.
1.2 基于索引图的 ANNS
在 ANNS 中, 索引图 (index graph) 是一种在查询精度与效率之间进行了良好平衡的索引结构 [16] . 其核心思想是
将原始高维向量数据构建为图, 使相似向量通过边相连接, 从而在图上通过沿着边的跳转逐步逼近查询向量的近
d d
邻. 给定一个向量集合 V = {v 1 ,v 2 ,...,v n } ⊂ R , 其中 v i 表示第 i 个向量, 其坐标为 x v i ∈ R . 基于此构建近邻图 G = (V,E),
E 连接每个点与其若干个近邻, 构成索引图结构. 如图 2 所示, 图 2(b) 展示了
其中每个顶点表示一个向量, 边集合
由图 2(a) 中的向量数据集所构建的索引图结构.

v 7
v 7 v 6 v 7 v 6
v 6
v 5
v 5 v 5 q
q q
v 3 v 4 查询向量 v 3 v 4 查询向量 v 3 v 4 查询向量
v 2 v 2 v 2
v 1 v 1
v 1
v 0 v 0
v 0
入口点
(a) 原始向量数据 (b) 向量索引图 (c) 索引图上的搜索过程
图 2 基于索引图的 ANNS 示意图

q, 首先从图中随机选取或使用启发式策略确定一
在基于索引图的近似最近邻搜索中, 针对给定的查询向量
个查询入口点 v start , 从该点出发, 算法将其邻居顶点按照与 q 的距离加入候选队列 L, 每轮选择候选队列 L 中与 q
l
∗ L 中前 个顶点均被访问. 令索引
最接近且未访问的点 p 进行拓展 (获取顶点的向量和邻居信息), 直到候选队列
图为 G(P,E), 其中顶点集 P 表示数据集中的所有点, 边集 E 定义了点之间的连接关系. 对于任意点 p ∈ P, 设其向
量为 x p , 查询向量为 , 距离函数为欧几里得距离 dist(p,q) =∥ x p − x q ∥ 2 . 若当前候选集合为 L ⊆ P, 访问集合为 S ⊆ P,
x q
则每轮扩展点选择如下:

p = argmind(p,q),
∗
p∈L\S
∗
∗ S ← S ∪{p }, 其中, ∗ p 的邻居顶点. 重复上述过程, 直到
∗
同时, 更新候选队列 L ← L∪ N out (p )、访问集合 N out (p ) 为
|L∩S | = l, 最终返回 L 中与 q 最接近的 k (k ⩽ l) 个顶点作为结果. 该策略被称为 Greedy Search, 在实际实现中也常
被改进为 Beam Search, 以提高并行 I/O 效率. 在图 2(c) 的示例中, 搜索过程从入口点 v 0 出发, 其 3 个邻居与查询
向量 q 的距离按升序排列为 v 1 ,v 3 ,v 2 , 这些点依次被加入候选集合 L. 首先选择距离最近的 v 1 进行拓展, 由于 v 3 已
在 L 中, 仅需将 v 1 的另一个邻居 v 4 加入 L. 此时候选集合 {v 2 ,v 3 ,v 4 } 中, v 4 与 q 的距离最小, 故被选为下一轮拓展点.
至此, 算法已成功定位到 q 的最近邻 . 为了查找 q 的 Top-k 近邻, 算法会继续按此策略拓展, 直至满足终止条件.
v 4
1.3 搜索过程的两阶段划分
ANNS 的查询过程呈现出显著的两阶段性特征 [21] . 如图 2(c) 所示, 在搜索到 q 的最近邻 v 4 之后, 由于需要进
一步查询剩余候选顶点以构成完整的 Top-k 返回结果, 因此还需要继续拓展搜索路径. 此时, 拓展路径可能逐渐远
离查询点 q 导致距离整体呈现上升趋势, 但由于搜索仍局限在局部候选区域的若干跳范围内, 且扩展仍倾向于优
先探索距离较近的顶点, 因此距离值通常只会在一个较小的区间内波动. 图 3 展示了在 100 万个向量的 SIFT 和
GIST 数据集上进行 ANNS 查询时, 查询点 q 与每轮拓展点 p 之间的欧氏距离随着拓展轮数的变化趋势. 图中的
∗
红点标注了查询过程中最接近目标向量的顶点出现的拓展轮数及对应的最小距离. 可以观察到, 在到达这一最小
距离点之前, 查询距离呈现快速下降趋势; 而在此之后, 距离变化逐步进入较为稳定的波动区间. 基于这一结果, 本
文在分析 ANNS 的查询过程中使用两阶段的概念.