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

王可 等: 面向批量更新的向量索引召回率优化 1095

● 基于枢纽识别的邻居补充. 应用修正规则后, 选取 C origina 中邻居数量不小于 M/2 的节点构成枢纽节点子集
l
H = {v|v ∈ C original ,|v.neighbors| ⩾ M/2}, 并将其合并入 C alpha , 形成最终的候选邻居集 C final = C alpha ∪ H.
修正剪枝规则的剪枝因子 α 决定了剪枝的宽松度, 其取值直接影响剪枝所得的候选邻居质量. 为此, 本方法基
于识别出的致密区域进行局部节点采样, 通过分析样本节点间距离分布特征, 自适应地确定适配当前数据集分布
的 α 值.
上述双重剪枝策略, 源于对 HNSW 算法中邻居剪枝策略的深刻理解. 向量搜索过程本质上是一种贪心搜索过
程, 其具有明显的路径依赖性, 即搜索着重于当前局部最优选择, 且搜索路线会影响最终结果, 因为每一步的选择
依赖于之前的路径. 这意味着, 若仅采用 α>1 的修正剪枝规则, 尽管增加了邻居连接的多样性, 但也可能因在迭代
早期引入了某个较远的邻居; 而改变后续的剪枝基准, 忽略了原生规则所能发现的高质量候选邻居. 因此, 本方法
提出的邻居选择策略, 可以实现更为精准的权衡. 算法以具备多样邻居的 C alph 为基础, 通过精准地补入 C origina 中
l
a
的枢纽节点来提升邻居的质量. 这种剪枝修正策略使得算法能够保留那些在原规则下可能因距离相近而被判定为
冗余的连接, 但这些连接对图的连通性和导航却至关重要. 通过这样的处理, 算法有效地缓解了过度剪枝效应. 同
时, 该策略还能保留原剪枝规则中较优质的邻居, 确保局部检索的精度.
3.3 算法实现与分析
下面介绍基于自适应细粒度剪枝策略的 HNSW 索引构建过程, 完整流程如算法 1 所示. 该算法接收的参数包
括: 待插入向量 v、索引参数 (邻居数量上限 M 和候选邻居扩展因子 efConstruction)、索引最高层级 maxLayer、
入口点 enterPoint、邻居度量参数 β 以及剪枝因子 α. 在向索引插入向量 v 后, 需同步更新局部和全局的距离指标.
算法 1 包含两个阶段. 第 1 阶段是入口点的定位 (第 5–8 行), 通过自顶向下的贪心搜索过程, 在各层级为待插
入节点 v 确定最优的搜索起始点 ep. 第 2 阶段是在各个层级 l 上的邻居构建 (第 9–22 行), 该阶段是算法的核心优
化部分: 第 1 步, 通过 SearchAtLayer 为 v 获取初始候选邻居集 tempRes (第 10 行). 第 2 步, 识别该节点是否处于致
密区域 (第 11、12 行): 首先, 通过 getAreaAvgDistance 计算该节点的区域邻居平均距离 area_mean_dist, 将其与全
局邻居平均距离 global_mean_dist[l] 进行比较, 若 area_mean_dist 低于 β·global_mean_dist[l], 则判定该节点处于
局部致密区域, 并对其实施双重剪枝的邻居选择策略 (第 13–18 行). 该策略先采用 α>1 的修正剪枝规则, 获取更多
样连接的候选邻居集 C alpha ; 在此基础上, 再采用 α=1 的原生剪枝规则以得到 C original , 并将其中邻居数大于 M/2 的
枢纽节点组成枢纽子集 H (第 15–17 行), 最终的候选邻居集 C fina 为 l C alph 与 a H 的并集 (第 18 行). 对于未处于致
密区域的节点, 则仅对其实施 α=1 的原生剪枝规则 (第 19–21 行). 在构建完 v 的邻居关系后, 其为新邻居构建反向
连接关系, 以增强图的局部连通性 (第 22–25 行). 最后, 更新索引的全局状态: 判断入口点是否需要更新, 若新节
点 v 的层级 level 超过了最大层级 maxLayer, 则将其设为新的全局入口点 (第 28–31 行).

算法 1. 基于自适应细粒度剪枝优化的 HNSW 索引构建算法 (Insertion).
输入: 待插入向量 v, 邻居数量上限 M, 候选邻居扩展因子 efConstruction, 索引最高层级 maxLayer, 入口点 enterPoint,
邻居度量参数 β, 剪枝系数 α.

1. begin
2. Queue<VectorID> tempRes // 存储搜索过程中的候选节点
3. level = getRandomLevel() // 为节点 v 随机分配的目标层级
4. VectorID ep = enterPoint // 初始化入口点
5. for l = maxLayer downto level−1 do: // 阶段 1: 自顶向下搜索, 为待插入层定位入口点
6. tempRes = SearchAtLayer(v, ep, M, 1, l)
7. ep = getClosest(tempRes, 1)
8. end for
9. for l = min(maxLayer, level) downto 0 do: // 阶段 2: 逐层构建邻居连接, 并实施自适应的细粒度剪枝优化