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

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

结构复杂性的重要指标, 能够揭示高维向量数据在局部区域的实际维度特征. LID 值较大通常表示更难区分这些
向量数据, 较高的 LID 给模拟相似向量写入场景带来了挑战.

表 2 实验数据集

数据集 样本数量 向量维数 内容 LID
GIST1M 1 000 000 960 Image 18.9
MSong 1 000 000 420 Audio 9.5
Enron 94 987 1 369 Text 11.7

● 实验环境. 本实验的硬件平台为: Intel(R) Xeon(R) Gold 6240M CPU @ 2.60 GHz, 内存 192 GB, 操作系统为
CentOS Linux 7.
● 评价指标. 实验中主要关注索引的检索精度、微观拓扑结构、索引构建开销及检索效率, 采用以下 4 个关
键指标.
(1) 召回率 (recall@K). 用于衡量检索结果的准确性. 其形式化定义为算法返回的 top-K 结果集与真实 top-K
最近邻集合之间交集的基数, 与 K 的比值. 实验中 top-K 的默认值为 10.
(2) 平均邻居连接数. 其定义为计算相似更新集中所有节点建立的出边数量的算术平均值, 用于验证本文所提
优化方法在修复相似向量连接稀疏的问题上的有效性.
(3) 索引构建时间. 记录了构建完整索引所需的时间, 直接反映了不同算法在索引构建阶段的计算开销.
(4) 查询执行时长/查询吞吐量 (QPS). 用于衡量检索的效率, 反映了索引处理查询请求的能力.
● 实验方法. 为了全面评估本文提出的基于图结构局部调整的自适应细粒度剪枝策略的效果, 本节的实验遵
循第 2.1 节的实验设置, 模拟批量插入相似数据的场景. 图 9 定义了实验场景和负载写入流程. 构建基础索引 (图 9
中的原始向量): 该过程使用原始向量构建 HNSW 索引, 未引入任何相似数据. 更新相似向量 (图 9 中的更新向量):
在基础索引的基础上, 批量插入相似数据负载. 基于以上实验设置, 分别构建两组索引: Batch 表示基于原 HNSW
算法构建的索引, Opt 表示应用本文优化方法改进的索引. 实验定义了多级相似数据负载, 各级的相似数据占比从
1% 递增至 5%. 为了模拟批量更新相似向量场景, 我们分别设置数据集的基础向量如下: GIST1M 为 10 万,
MSong 为 10 万, Enron 为 9 万.

Batch 原始向量
向量数据写入顺序 更新向量
调整邻居关系的向量
Opt

图 9 数据写入场景的实验负载

优化方法的实验流程通过对这两个索引施加相同的、批量相似数据负载操作展开. 具体而言, 实验将依次批
量地向基础索引写入新数据, 从而构建相似数据占比为 1%、2%、3%、4% 以及 5% 的 5 个增量更新的批量负载.
在写入每批数据后, 对两个索引的当前状态进行召回率、邻居关系分析等测试. 该测试将通过相应的相似查询集,
对比分析两种算法在关键指标上的性能表现. 实验过程按如下方式进行: 首先, 实验测量并比较它们的召回率
(recall@K) 与查询执行时长, 定量评估本文方法在提升检索精度与速度方面的具体优势. 其次, 实验将测量并对比
相似数据节点的平均邻居连接数, 从微观层面验证本文方法在修复连接稀疏化问题上的优化效果.
4.2 算法性能实验结果与分析
4.2.1 平均召回率的结果与分析
在批量插入相似数据场景下, 我们在多个数据集上开展横向对比实验, 以评估本文方法的性能表现. 实验比较