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

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

原生 HNSW 与本文优化方法的召回率 (recall@K), 实验负载为第 4.1 节中定义的 5 类负载.
图 10 展示了 GIST1M 数据集的实验结果. 在各组索引参数 (M 和 efC) 与搜索深度 (efSearch) 下, 经本文方法
优化的索引召回率在所有负载阶段 (相似数据占比 1%–5%) 均优于原 HNSW 索引, 并且性能衰减速率也有所降
低. 例如, 初始索引参数为 M=24, efC=64 时, 当 efSearch 为 100 时, 随着相似数据占比的增加 (2%–5%), 召回率提
升分别为 2.41%、2.58%、3.02% 和 2.35%; 在 efSearch 为 150 时, 随着相似数据占比的增加 (2%–5%), 召回率提
升分别为 2.28%、3.06%、3.73% 和 3.51%. 综上所述, 在不同相似数据占比下, 索引的检索召回率都得到不同程度
的提升. 在写入相似数据占比较小时 (1%), 召回率的变化幅度不大. 这表明该优化方法不仅提升了基础检索性能,
还减缓了持续插入相似数据对索引性能的损害.

0.99 0.99 0.99
Batch Opt Batch Opt Batch Opt
0.97 0.97 0.97
召回率 0.95 召回率 0.95 召回率 0.95
0.93
0.93
0.93
0.91 0.91 0.91
0.89 0.89 0.89
0.87 0.87 0.87
0.85 0.85 0.85
1 000 2 000 3 000 4 000 5 000 1 000 2 000 3 000 4 000 5 000 1 000 2 000 3 000 4 000 5 000
(1%) (2%) (3%) (4%) (5%) (1%) (2%) (3%) (4%) (5%) (1%) (2%) (3%) (4%) (5%)
相似向量数量 相似向量数量 相似向量数量
(a) ෬ႄҕඔ M=24, efC=64, efSearch=100 (b) ෬ႄҕඔ: M=24, efC=64, efSearch=150 (c) ෬ႄҕඔ: M=24, efC=64, efSearch=200
1.00 1.00 1.00
0.98 0.98 0.98 Batch Opt
0.96 Batch Opt 0.96 Batch Opt 0.96
0.94
召回率 0.92 召回率 0.94 召回率 0.94
0.92
0.92
0.90
0.88 0.90 0.90
0.88
0.88
0.86 0.86 0.86
0.84 0.84 0.84
0.82 0.82 0.82
0.80 0.80 0.80
1 000 2 000 3 000 4 000 5 000 1 000 2 000 3 000 4 000 5 000 1 000 2 000 3 000 4 000 5 000
(1%) (2%) (3%) (4%) (5%) (1%) (2%) (3%) (4%) (5%) (1%) (2%) (3%) (4%) (5%)
相似向量数量 相似向量数量 相似向量数量
(d) ෬ႄҕඔ M=16, efC=32, efSearch=64 (e) ෬ႄҕඔ M=16, efC=32, efSearch=100 (f) ෬ႄҕඔ M=16, efC=32, efSearch=150
图 10 GIST1M 数据集的平均召回率

在索引配置为 M=24, efC=64 时, 增大搜索参数 efSearch (100–200), 召回率的提升幅度呈现出增加的趋势
(>3%). 因为增大 efSearch, 会增加搜索的深度, 这样向量选择邻居时候选集的质量得到了改善, 本文方法保留了原
规则中的优质邻居, 即枢纽节点, 因此, 有助于进一步提升改善向量的邻居关系质量. 在索引配置为 M=16, efC=32 时,
索引的提升幅度相对减小 (约为 1%–2%). 索引配置参数较小时, 召回率水平和邻居质量都受到了影响.
下面我们分析索引参数配置对索引的检索召回率水平的影响. 在 M=16, efC=32, efSearch=100, 相似数据占比
为 3% 时, 索引的平均召回率水平约为 88%; 在 M=24, efC=64, efSearch=150, 相似数据占比为 3% 时, 索引的平均
召回率水平约为 91.4%. 两种条件下索引的平均召回率相差 3.4%, 而应用本文的优化方法后, 召回率的差距为
5.5%, 当索引参数较小时, 图的质量受到了一定的影响, 这与 HNSW 索引的原理特性相符合. 同时, 这也进一步表
明本文方法能有效缓解批量插入场景下的召回率下降问题.
我们在 MSong 和 Enron 数据集上进行了相同的性能比较, 实验结果如图 11 和图 12 所示. 在 MSong 数据集
上, 随着相似数据占比的增加 (2%–5%), 在 M=16, efC=32, efSearch=64 时, 召回率平均提升水平为 3.9%; 在 M=24,
efC=64, efSearch=100 时, 召回率平均提升水平为 4.9%; 在 M=48, efC=100, efSearch=100 时, 召回率平均提升水平
为 8%. 在 MSong 数据集上, 随着相似数据占比的增加, 本文方法整体上表现出较好的召回率提升效果. 比较不同
索引参数对本文方法的影响, 当索引参数较小 (M=16, efC=32) 时, 索引的召回率水平偏低, 图质量不高, 其召回率
提升不高 (3.9%); 当索引参数较大 (M=48, efC=100) 时, 召回率平均提升水平可达 8%. 这与 GIST1M 数据集上的
表现相同, 当索引配置参数较小时, 召回率水平和邻居质量都受到了影响.
当 efSearch 分别为 100、150 和 200 时, 由 M=48, efC=100 构建索引的平均召回率的上升幅度分别为 8.38%、