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

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

4.2.2 相似数据邻居数量的结果与分析
本节针对批量插入相似向量引发的连接稀疏化问题, 通过对比优化前后平均邻居连接数指标的变化, 验证了
本文方法对向量邻居关系具有较好的修复能力. 实验基于 GIST1M、Enron 和 MSong 数据集, 表 3 为索引邻居关
系的分析结果 (相似数据占比为 1%–5%), 实验结果表明, 所有数据集均显著改善, 相似节点的邻居的连接密度和
邻居质量均有所提升, MSong 数据集提升最显著.

表 3 相似向量邻居数量的变化

Batch平均邻居 Opt平均邻居 Batch邻居数量较小 Opt邻居数量较小
数据集 索引参数
数量 数量 向量的占比 (%) 向量的占比 (%)
GIST1M M=24, efC=64 6.4 7.7 60 59
Enron M=24, efC=64 9.0 9.7 53 48
MSong M=48, efC=100 4.6 12.1 95.7 78.5

在 GIST1M 和 Enron 数据集上, 相似向量的平均邻居数量分别为 6.4 和 9.0, 优化方法将其提升至 7.7 和 9.7.
在 MSong 数据集上, Batch 场景下 HNSW 的平均连接数仅为 4.6, 而本文方法将其提升至 12.1, 同时, Batch 场景下
邻居数量较小向量的占比高达 95.7%, 本文方法将其降低至 78.5%, 低连接的向量数量大大降低. 因此, 本文提出
的双重剪枝策略, 通过剪枝优化方法和保留枢纽向量, 不仅可以提高邻居的基础数量, 而且有助于保留关键连接
边 (枢纽向量) 以提高邻居质量, 即使在大量相似数据积累的负载 (相似数据占比为 5%) 下, 仍能维持较高的图连
通性. 这将有效地缓解图结构的拓扑稀疏化问题, 进而提升检索的召回率.
4.3 开销与效率评估
本节进一步评估了索引的构建开销和计算效率. 实验对比了 Batch 和 Opt 两个场景下 HNSW 索引的构建时
间和查询时间/查询吞吐量 (QPS) 两个关键指标.
● 索引构建时间. 表 4 展示了原方法与本文优化方法在索引构建时的平均耗时情况, 为精确度量构建的开销,
索引使用单线程方式构建. 本文方法会引入额外的计算成本, 在构建阶段会增加少量的计算时间. 实验结果表明,
在所有数据集中, 本文方法与原 HNSW 索引的构建时间均保持在同一水平. 例如, 在 GIST1M 数据集上, 平均构建
时间均为 98 s; 在高维向量 Enron (1 369 维) 上, 平均构建时间仅增加 4.2 s.

表 4 索引构建开销

数据集 索引参数 Batch构建时间 (s) Opt构建时间 (s)
GIST1M M=24, efC=64 98.4 98.5
Enron M=24, efC=64 97.8 102
MSong M=48, efC=100 78.6 80.4

参数 M 与 efConstruction 会显著影响索引的构建时间. 当采用更大的参数 (如 M=48, efC=200) 时, 其邻居数量
和搜索范围均会扩大, 其构建时间也相应地增加. 但本文方法的目标是优化邻居关系, 在高参数配置下, 索引的邻
居关系已经得到了改善, 因此额外计算成本也会相应地减少, 所以, 本文方法的计算开销不会因较大索引参数带来
的基础构建开销的增加而产生明显的增长.
上述观测结果符合理论预期: 本文方法的额外开销主要是对少量枢纽节点执行邻居选择策略, 在全流程中均
摊的计算开销较低, 最终实现以计算时间换取查询精度的显著提升.
● 查询执行时长/查询吞吐量 (QPS). 在 Batch 和 Opt 场景下, 表 5 和表 6 分别展示了在不同查询参数 (efSearch
和 top-K) 下, 索引的检索效率. 其中, efSearch 为查询时动态候选集的大小, top-K 为结果集的数量. 表 5 和表 6 中
的检索时间为: 在对应场景下, 执行查询集的总检索时长, 查询集的大小为 1k.
实验数据显示, 在检索 GIST1M 和 Enron 向量索引时, 本文方法的检索时长会降低, 索引的 QPS 得到了提升.
本文方法中的双重剪枝策略和保留枢纽向量可以改善邻居关系, 从而减少搜索步长, 达到提升召回率和搜索最优
邻居的目的. 本文方法在应用到 MSong 数据集时, 增加了较多的邻居数量 (如表 3 所示), 这使得查询搜索的候选
向量增多, 因此增加了搜索的开销.