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

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

节深入地剖析这些现象, 揭示其背后的原因, 从而为第 3 节的优化方法提供理论基础与数据支撑.
2.1 实验设置
在批量插入相似数据场景下, 为分析 HNSW 索引性能下降的原因, 本节设计了对比实验, 模拟该场景来评估
索引的性能和量化索引内部的结构特征. 实验从宏观性能指标与微观拓扑结构两个维度, 定量地揭示影响 HNSW
索引召回率的原因. 我们选择了多个广泛使用的代表性向量数据集, 包括 GIST1M [41,42] 、MSong (Million Song) [43]
和 Enron [44] (详见第 4.1 节). 这些数据集在维度、分布特性和内在结构上存在显著差异, 覆盖了较多实际应用场
景. 接下来, 我们将详细阐述数据处理、负载构建与评价指标这 3 个方面的内容.
● 生成相似数据与划分数据集. 为模拟真实应用中的批量插入场景, 本节提出了构造相似数据的方法. 相似数
据在较小的距离空间内存在微小变化, 因此采用一种基于维度扰动的数据生成方法. 该方法以原始数据集中的向
量作为母向量, 为其生成距离上较近的相似向量. 该生成过程如下: (1) 扰动窗口: 对于选定的母向量 v∈R , 确定一
d
个待扰动的维度子空间, 其宽度 w 由一个预设比例 r w (默认为 0.3) 控制, w 的计算方式为 w = ⌊r w ·d⌋. 为模拟真实
数据中特征重要性分布的随机性, 窗口起始维度 d star 从均匀分布 U 1 中采样确定; (2) 引入有界均匀扰动: 在维度
t
窗口 [d start , d start +w) 内, 对每个维度添加服从均匀分布 U 2 的随机扰动, 窗口外的维度值保持不变. 该方法生成的向
量为实验中的更新向量. (3) 构造查询集: 将以上扰动机制应用到原始查询集, 生成用于评估检索性能的相似查
询集.
● 构建批量插入相似数据场景. 在持续写入相似数据 (上述方式产生相似数据) 时, 为精确捕捉 HNSW 索引在
性能以及索引结构上的变化情况, 本节设计了一种增量式的写入负载与评估流程. 该流程实现了多次批量插入相
似数据场景, 记录各级负载召回率的变化情况. 在批量插入相似向量时, 通过精确计算 HNSW 索引中数据特征的
变化, 进一步分析召回率退化的原因.
实验场景和负载写入流程如下. 我们控制相似数据负载中相似数据占比, 以模拟批量写入相似数据的实际应
用场景. 构建基础索引: 该过程使用原始向量构建 HNSW 索引, 未引入任何相似数据. 更新相似向量: 在基础索引
的基础上, 批量插入相似数据负载. 实验定义了多级相似数据负载, 各级的相似数据占比从 1% 递增至 5%. 其中,
Batch 表示在原始向量的基础上, 连续写入相似向量的场景. 各个数据集的基础向量分别如下: GIST1M 为 10 万,
MSong 为 10 万, Enron 为 9 万.
在写入每个负载 (相似数据占比为 1%–5%) 后, 实验将采用相似查询集 (默认 1 000 条), 计算当前索引的召回
率, 并获取邻居关系信息. 实验中设计增量式的写入负载与评估流程, 在随着相似数据在索引中占比的持续提升的
过程中, 捕捉索引中呈现的召回率退化现象, 重点关注索引的以下指标: 检索召回率和相似数据邻居数 (详见第
2.3 节).
● 检索召回率. 用于衡量索引的宏观检索精度. 向量检索主要关注查全率, 即 recall@K, 其定义为算法返回的
top-K 结果集与真实 top-K 最近邻集之间交集的占比. 该指标直观地反映了索引成功找回真实近邻的能力.
2.2 批量插入场景下召回率的变化
本节展示了在持续插入相似数据时 HNSW 索引检索召回率的变化情况. 实验场景如第 2.1 节所述, 我们在相
似数据占比为 1%–5% 负载的写入过程中测量召回率 (recall@K) 的变化.
图 4 展示了在插入相似数据过程中, GIST1M 数据集在索引参数为 M=24, efC=64 时召回率的变化情况. 图中
每条曲线 (Batch-efSearch) 对应特定的查询深度参数 efSearch 以及 top-K (默认为 10), 纵坐标表示查询的召
回率.
● 实验现象与数据分析. 实验结果表明, 随着相似数据占比的增加, HNSW 索引的检索召回率呈现出逐渐下降
的趋势, 该现象在 3 个数据集以及不同索引参数下都普遍存在. 如图 4 所示, 当 efSearch 为 100 时, 相似数据占比
为 1% 时的查询召回率约为 0.9, 在相似数据占比从 1% 提升至 5% 的过程中, 召回率持续下降, 最低为 0.89, 其降
幅达到 9%. 即便在 efSearch 为 150 和 200 时, 5% 负载的召回率 (0.899 和 0.907) 相较于 1% (约 0.985) 依然存在显
著差距. 上述现象反映了批量插入相似数据对 HNSW 检索精度存在持续性损害.