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

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

(2) 双重剪枝的邻居选择策略. 对致密区域的节点, 协同应用原生剪枝规则与修正的 α 剪枝规则, 通过融合两
种规则所选择的候选邻居集合, 实现精度保障与探索强化的双重目标. 该方法有以下两方面的收益: 一方面维持关
键局部近邻, 以提高搜索准确性; 另一方面引入结构多样性, 增强对复杂连接模式的探索能力.
(3) 基于枢纽识别的邻居补充. 为了保留质量较高的邻居, 识别出应用原生剪枝规则获取的邻居结果中的枢纽
节点, 将具有丰富连接的枢纽作为候选邻居. 此操作有助于提升局部拓扑的质量.
本文的主要贡献概括如下.
(1) 深入分析了 HNSW 索引在批量插入相似向量时的召回率退化问题. 通过深入的实验验证, 揭示了索引性
能下降的原因: 由局部区域过度致密所引发的过度剪枝效应以及相似向量的连接稀疏化.
(2) 针对上述问题, 提出了一种基于图结构局部调整的自适应细粒度剪枝策略. 该策略构建完整优化框架, 通
过数据驱动识别、双重剪枝的邻居选择以及基于枢纽识别的邻居补充方法, 有效地修复相似向量批量插入导致的
结构损伤. 通过动态维护 HNSW 索引的邻居关系, 提升召回率.
(3) 在多个公开数据集上, 设计并进行详尽的实验以验证本文的优化方案. 实验结果表明, 在批量更新场景下,
相较于原 HNSW 方法, 本文的优化方法在未引入显著查询开销的前提下, 将召回率稳定提升 1%–4%. 实验验证了
本文方法的有效性与高效性.
本文第 1 节描述背景和相关工作. 第 2 节通过实验发现问题, 并对现象和实验数据进行深入分析. 第 3 节详细
阐述本文所提出的索引结构优化方法及其算法实现. 第 4 节进行实验评估. 第 5 节总结本文.

1 研究背景与相关工作

第 1 节介绍本文的研究背景与相关工作. 第 1.1 节对近似最近邻搜索和向量索引进行概述. 第 1.2 节重点聚焦
于基于图的向量索引, 系统性地梳理其发展脉络与核心技术. 第 1.3 节综述与 HNSW 索引召回率优化相关的关键
工作, 为本文提出的优化方法奠定基础.
1.1 近似最近邻搜索和向量索引

随着当代人工智能技术的发展, 向量嵌入已成为表征文本、图像、音视频等复杂非结构化数据的标准范式.
在这种范式下, 现实世界中的用户推荐、语义相似性检索以及多模态交互 [33] 等复杂场景, 能够被高效地转化为高
维向量空间中的几何距离计算问题. 然而, 在高维空间中进行精确的暴力搜索会遭遇维度灾难, 其计算复杂度随着
数据规模和维度的增长而急剧上升, 无法满足现代人工智能系统对低延迟、高吞吐的应用需求.
为了应对这一挑战, 近似最近邻搜索技术应运而生. 其核心思想是, 在可控的精度损失范围内, 在大规模高维
d d
数据中高效地检索与查询点最接近的向量数据. 其定义如下: 在度量空间 R 中, 给定数据集 S = {x 1 , x 2 ,..., x N } ⊆ R ,
d c. ANNS x ∈ S 满足:
∗
查询 q ∈ R 以及近似因子 的目标是找到一个或多个点

∗
dist(q, x ) ⩽ c·dist(q, x true ) (1)
其中, dist(·,·) 是空间 R 的距离度量 (如欧氏距离、余弦相似度等); x true 是 q 在 S 的精确最近邻.
d
向量索引是支撑高效近似最近邻搜索的核心数据结构. 其根本目标是通过对数据集进行预处理, 构建一种能
够极大地加速查询过程的辅助性结构. 在索引构建阶段, 向量索引将原始高维向量组织起来, 例如, 通过建立向量
数据之间的拓扑邻接关系 (如图索引) 或空间划分关系 (如树索引、倒排索引). 这种预先建立的结构, 使得在查询
阶段可以应用高效的剪枝或路由策略, 从而避免对整个数据集进行暴力扫描, 将搜索范围剪枝至一个很小的高相
关性候选子集中, 最终实现数量级的查询加速.
1.2 基于图的向量索引
在前述多种向量索引中, 基于图的索引已成为当前最受关注和应用最为广泛的一类方法. 其核心思想是将数
据集中的向量建模为一个邻近图 G = (V, E), 其中, 顶点集 V 代表数据向量, 边集 E 表示向量间的邻近关系. 通过
这种方式, 近似最近邻搜索问题被转化为在图 G 上的遍历搜索问题. 相较于其他索引方法, 图索引因其在查询效
率、召回精度与可扩展性之间取得了卓越的性能均衡而成为学术界与工业界的主选方案. 图索引的应用包含构建