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

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

构缺陷, 即相似向量的连接稀疏化. 该问题形成的原因如下: 在写入较多相似向量时, 因过度剪枝导致初始邻居连
接稀疏; 在后续插入向量的过程中, 当向量搜索过程收敛至该低连通区域时, 进一步加剧了过度剪枝效应, 新节点
邻居的质量又进一步受到了抑制.

GC > GD: 剪枝 GC GD > GE: 剪枝 GD B
A
B
B A
A
目标点
G C G C G C 入口点: A
E E E 目标点: G
D D 停止 D 未探索: E

(a) C 选取邻居 (b) D 选取邻居 (c) 查询过程
图 6 启发式规则造成的过度剪枝

过度剪枝和连接稀疏化问题持续地累积, 最终会导致局部子图呈现出两个拓扑缺陷: 其一, 内部连接不足, 正
如第 2.3 节的实验数据所示, 区域内节点的平均邻居连接数远低于邻居数量上限 M; 其二, 外部连接缺失, 即节点
因邻居选择高度局限于簇内, 而难以建立起指向外部区域的关键性长连接, 阻碍了全局导航. 这一连接稀疏的局部
造成了性能瓶颈: 当查询路径进入该区域后, 因缺乏多样的路径选择, 贪心搜索易陷入局部最优或过早终止, 从而
解释第 2.2 节观测的召回率持续下降现象.
3 基于图结构局部调整的自适应的细粒度剪枝策略

第 2 节揭示了批量插入相似数据时 HNSW 索引结构出现的问题: 过度剪枝和相似向量连接稀疏化, 这也是该
场景下索引的性能瓶颈. 针对此问题, 本文提出一种基于图结构局部调整的自适应细粒度剪枝策略. 该方案从局部
拓扑入手以应对过度剪枝问题, 其核心设想在于设计一种能依据局部数据密度进行动态调整的自适应细粒度剪枝
策略. 方法的核心遵循识别与修复模式: 通过数据驱动的预分析过程, 精准定位待干预的致密区域, 该区域用于识
别出相似数据聚集的区域, 是划分相似向量与基础向量的依据. 针对该致密区域内的节点, 实施双重剪枝策略. 双
重剪枝策略包括以下要点: 应用修正规则, 选择出候选邻居, 修正规则是放宽向量插入过程中邻居选择的剪枝的限
制条件, 有效抑制过度剪枝效应; 筛选出应用原规则时的枢纽节点, 即邻居数高于平均水平的向量, 并将其与修正
后的候选邻居合并, 保留潜在的有效连接. 该策略显著优化了稀疏连接下邻居的质量, 从而缓解连接稀疏化问题,
实现邻居选择中精度与多样性的有效权衡. 双重剪枝的邻居选择策略, 其核心在于协同应用原生与修正的两种剪
枝规则, 并合其结果, 识别并保留原生规则中的枢纽向量, 以提高邻居连接的质量与数量.
3.1 局部致密区域识别方法
首先, 识别方法需要准确地量化局部拓扑的密度, 精准地识别出因相似数据聚集而形成的局部致密区域, 才能
自适应地应用剪枝策略. 一种直接的识别方式是: 定义待插入节点的一跳邻居平均距离, 即该节点与其所有候选邻
居间的平均距离 (图 7(a)). 然而, 该方式受候选集中异常点 (距离过小或过大) 的扰动较大, 严重影响识别结果的准
确性和稳定性.
为此, 本文提出一种更具鲁棒性的识别指标——局部平均距离, 即区域邻居平均距离 ( area_mean_dist). 其核
心思想为, 通过聚合节点邻域的整体拓扑信息而不是只使用该节点自身的连接信息来评估局部区域的密度 (图 7(b)).
具体计算方式如下: 计算待插入节点候选邻居的一跳邻居平均距离, 然后计算它们的平均值. 该度量机制能够有效
平滑因异常候选点引入的噪声. 该方式综合考虑了整个候选邻域的拓扑稠密特征, 具有一定的鲁棒性, 从而能够更
准确地识别出向量的真实聚集区域, 减少误判的概率.
全局平均距离定义为全局邻居平均距离 (global_mean_dist[l]), 即对于索引的特定层级 l, 所有已存连接的长度
的算术平均值. 为保证效率, 系统仅为每一层级 l 记录当前所有连接的总数和总距离长度, 就可以以增量方式计算