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

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

10. tempRes = SearchAtLayer(v, ep, M, efConstruction, l)
11. area_mean_dist = getAreaAvgDistance(v, l) // 计算区域邻居平均距离, 以感知局部区域密度
12. if (area_mean_dist < β·global_mean_dist[l]) then: // 对致密区域的节点, 实施双重剪枝的邻居选择策略
13. C_original = getNeighborsByHeuristic(efConstruction, 1)
14. C_alpha = getNeighborsByHeuristic(efConstruction, α)
15. for v i in C_original do: // 将原生规则所选的枢纽节点合并入最终候选邻居集
16. if |v i .neighbors| ≥ M/2 then:
17. H = H ∪ {v i }
18. C_final = C_alpha ∪ H
19. else: // 对未处于致密区域的节点, 仅实施原生剪枝规则
20. C_final = getNeighborsByHeuristic(efConstruction, 1)
21. end if
22. for v i in v.neighbors do: // 为新建立的邻居构建反向连接
23. reConnection(v i , v)
24. getNeighborsByHeuristic(efConstruction, α)
25. end for
26. ep = getClosest(tempRes, 1) // 更新下一层的入口点
27. end for
28. if (level > maxLayer) then: // 设置新的全局入口点
29. maxLayer = level
30. enterPoint = v
31. end if
32. end

● 开销分析. 本算法在设计上严格控制了开销. 在存储开销方面, 额外存储空间仅包含各层级图结构的全局平
均距离 global_mean_dist[level], 其空间复杂度为 O(1), 对系统整体存储需求的影响可忽略不计. 在计算复杂度方
面, 主要开销来自 getAreaAvgDistance 函数, 而通过合理地设置 efConstruction 和 M 参数, 可以有效控制图结构的
规模, 从而将该计算的时间复杂度控制在可接受范围内. 根据多个数据集上的实验观察, 被识别为致密区域并经过
剪枝优化的节点占比较低 (仅为数据集的 0.5%–2%). 因此, 该优化方法引入的额外计算开销非常小, 得以维持
HNSW 索引对数级别的插入复杂度.
本节详细阐述了一种基于图结构局部调整的自适应细粒度剪枝策略, 通过识别与修复的闭环机制, 有效缓解
了因过度剪枝导致的局部拓扑结构稀疏和召回率退化问题. 该策略能够动态地适应局部数据分布的变化: 在数据
致密区域通过放宽剪枝条件主动保留了关键的导航连接; 而在其他区域则仍实施原生 HNSW 剪枝规则.

4 实验分析

4.1 实验设置

● 实验数据集. 为了全面评估本文方法的效果, 我们在多个公开数据集 (详见表 2) 上开展实验. GIST1M 包含
100 万个 960 维 GIST 描述符 [41] , 这些描述符是基于一组感知维度从原始图像中提取的低维向量数据. MSong 涵
盖 100 万首西方流行音乐的音频特征 (节奏、响度、淡入淡出时间等), 适用于音乐推荐系统研究. Enron 包含安然
公司内部 150 名用户数据, 其中大多数是高层管理人员, 涵盖约 50 万封真实电子邮件及其元数据, 适用于文本分
析与社交网络研究, 数据维度较高 (1 369). 此外, 局部本征维度 (local intrinsic dimensionality, LID) 是衡量数据局部