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

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

该全局距离. 在新增一条连接时, 仅需以 O(1) 的复杂度更新这两个统计量. 该方式使得全局平均距离通过较少计
算获得, 避免了重新计算全局距离的开销.

最小距离、最大距离平均距离 节点间的平均距离度量区域覆盖情况

A B

A
...
C

(a) 基于邻居平均距离的α剪枝 (b) 基于区域平均距离的α剪枝
图 7 局部过度致密区域的识别方法

基于以上指标, 我们设定了区域邻居平均距离与全局平均距离的比较规则, 用于识别低密度区域. 具体识别方
式如下: 新插入节点 v 的区域邻居平均距离 area_mean_dist 与该层的全局平均距离 global_mean_dist[l] 满足如下
不等式:

area_mean_dist < β·global_mean_dist[l] (4)
若符合公式 (4) 则判定节点 v 当前处于局部致密区域. 对于新写入的向量, 在满足公式 (4) 时, 为其应用修正
的启发式剪枝规则.
识别的精准度与阈值参数 β 的设定紧密相关, 这也直接决定了算法对局部致密区域的敏感度. β 为控制识别
敏感度的超参数, 数据无关的 β 值难以感知不同数据集的内在分布特性. 为此, 本文应用数据驱动的 β 值自适应选
择方法: 在构建索引时, 从向量中抽取一定量样本数据, 并计算每个样本向量的区域邻居平均距离 area_mean_dist
与全局邻居平均距离 global_mean_dist[level] 的比值. 然后, 分析数据的分布情况, 选择合适的分位数作为 β 的取
值. 该方法使得 β 不再是一个经验性的固定值, 而是能够反映当前数据集实际分布与内在统计特性的动态参数. 此
设计确保优化策略的激活具备明确的量化依据.
3.2 双重剪枝的邻居选择策略
针对识别到的致密区域节点, 本文采用一种双重剪枝的邻居选择策略. 该策略的核心在于融合两种规则的剪
枝结果, 在提升连接多样性的同时, 保留关键的枢纽向量, 从而实现局部拓扑的修复和选择高质量邻居.
● 双重剪枝的邻居选择策略. 对于新写入节点, 算法协同应用原生与修正的剪枝规则, 保留潜在的有效连接,
以提升稀疏连接情况下邻居的质量.
(1) 原生剪枝规则 (α=1): 即标准的 HNSW 启发式剪枝规则. 此规则所选的候选邻居集合记为 C original .
(2) 修正剪枝规则 (α>1): 如图 8 所示, 该规则通过引入一个大于 1 的剪枝因子 α, 选择性地放宽了剪枝条件. 其
具体规则如下: 对于待插入节点 v, 仅当一个候选邻居 v'与结果集 R 中某个已选邻居 v i 满足 α·dist(v ,v i ) > dist(v ,v)
′
′
时, v'才被视为冗余邻居并予以剪枝. 此规则用于筛选出一组更具方向多样性的候选邻居集合, 记为 C alpha .

B A B A

G G
C C
局部调整参数α
扩大搜索范围
E E
D D

图 8 修正的启发式剪枝规则