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

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

通过边连接相似的数据点, 从而形成一个图结构. 通过图的遍历和搜索, 可以快速找到与查询点相似的数据点. 图
的基本搜索策略是基于 best-first-search [11] 的贪心搜索策略, 如算法 1 所描述, 在搜索中通过维护一个队列实现在
图上的搜索, 在 HNSW [28] 的实现中使用两个队列, 此处一个队列参考了在 NSG [17] 图中的实现, 其搜索方式等价. 通
过不断地检查搜索队列中的点的邻居节点来更新搜索队列, 实现在图上的遍历操作. 通过控制队列的大小可以控
制在图上进行遍历的程度. 搜索终止之后会将队列中的前 k 个结果返回, 作为最终的结果.

算法 1. 贪心搜索算法 (best-first-search).

输入: 图 G=(V, E), 查询点 q, 返回近邻数量 k, 搜索队列 Q, 搜索队列大小 W, 初始点 ep;
输出: 查询 q 的 k 个近似最近邻.

1. 用 ep 初始化 Q, 初始化访问标记 V
2. while Q 中有邻居没有被检查的点 do
3. x = Q 中离 q 最近, 同时邻居节点还没有被检查的点;
4. 标记 x 的邻居被检查;
5. for x 的每个邻居 y do
6. if (y 在 V 中) continue;
7. 计算 y 和 q 的距离, 更新 Q, 保留最近的 W 个点;
8. 在 V 中标记 y 被访问;
9. end for
10. end while
11. 返回 Q 中距离查询最近的 k 个点作为搜索结果

2.1.1 构建策略
HNSW 算法 [28] 是基于图的索引组织方法中的一种, 被广泛应用于各大数据库 (以支持近似最近邻搜索). 它通
过构建多层次的图结构来加速搜索过程. HNSW 利用导航小世界图的思想, 在 NSW 基础上将其扩展为具有多层
导航结构的图, 每一层都是一个图结构, 底层图包含所有数据点, 而上层图则是对底层图的摘要表示. HNSW 取得
了相较于 NSW [41] 以及 KNN 图 [42] 更快的搜索速度.
HNSW 采用增量式的构建方法, 将点逐个地插入到图中. 每个点在插入时会随机选择一个层数, 从此层开始
逐层插入该点直至最底层. 在每一层中通过贪婪搜索算法搜索到相似的 m 个点, 作为当前点的候选邻居节点, 然
后根据选点策略选择若干点作为当前点的邻居节点. 具体策略为从距离要插入的点最近的候选点开始检查, 当且
仅当候选点与任何已经成为邻居节点的对象的距离比与要插入对象的距离更近时, 才将该候选点作为邻居节点.
如图 1 所示, P 2 是 P 1 的邻居节点, 但是 P 3 距离 P 2 更近, 因此 P 3 不能成为 P 1 的邻居节点. HNSW 的搜索方法是
逐层进行搜索, 从最高层开始, 每层通过贪婪搜索定位到下一层的入口点 (搜索获得的最近的邻居), 当搜索最底层
时, 将队列大小设置为 ef, 执行贪心搜索策略, 返回找到的最近的 k 个点作为搜索结果, 通过设置不同 ef 参数值可
以平衡效率和精度.

P 2 P 2
P 2 ′
P 1 P 1
P 3 P 3
3τ
P 4 P 4
(a) MRNG (b) τ-MG
图 1 MRNG [17] 和 τ-MG [43] 邻居节点构建策略