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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(3):1084−1103 [doi: 10.13328/j.cnki.jos.007519] [CSTR: 32375.14.jos.007519] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
面向批量更新的向量索引召回率优化

王 可 1 , 胡思劼 1 , 胡卉芪 1 , 赵明昊 1 , 魏 星 2 , 屠要峰 2 , 周 烜 1

1
(华东师范大学 数据科学与工程学院, 上海 200062)
2
(中兴通讯股份有限公司, 广东 深圳 518057)
通信作者: 赵明昊, E-mail: mhzhao@dase.ecnu.edu.cn

摘 要: 近似最近邻搜索 (approximate nearest neighbor search, ANNS) 是支撑向量数据库、推荐系统及大语言模型
等上层应用的关键技术. 其中, 分层可导航小世界 (hierarchical navigable small world, HNSW) 图索引通过构建层级
化结构, 迅速定位结果至目标区域, 从而以较低的计算成本实现较高的检索召回率. 然而, 现有 HNSW 算法主要面
向静态数据检索场景而设计, 而忽略了数据更新对检索性能的影响. 通过对现实数据集的研究发现, 向量数据库中
的数据通常以批量方式进行更新, 其相似特性会削弱 HNSW 算法中启发式剪枝的有效性, 并诱发相似向量连接的
稀疏化问题, 共同造成查询召回率的显著下降. 针对上述问题, 提出一种基于图结构局部调整的自适应细粒度剪枝
策略, 构建了融合识别与修复机制的优化方案. 首先, 在识别阶段, 通过计算区域邻居距离量化局部拓扑密度, 从而
精准定位待干预的致密区域. 其次, 在修复阶段, 针对处于致密区域的枢纽节点, 采用双重剪枝的邻居选择策略: 协
同应用原生的与修正的启发式剪枝规则, 合并两种规则的结果集以在保证检索精度的同时提升邻居连接的多样性,
有效缓解过度剪枝与连接稀疏化问题. 在多个公开数据集上的实验结果表明, 所提方法对数据更新频繁的场景具
备良好的适应性, 在维持查询延迟和吞吐量稳定的前提下, 实现了 1%–4% 的召回率提升.
关键词: 近似最近邻搜索; 向量检索; 图向量索引
中图法分类号: TP311

中文引用格式: 王可, 胡思劼, 胡卉芪, 赵明昊, 魏星, 屠要峰, 周烜. 面向批量更新的向量索引召回率优化. 软件学报, 2026, 37(3):
1084–1103. http://www.jos.org.cn/1000-9825/7519.htm
英文引用格式: Wang K, Hu SJ, Hu HQ, Zhao MH, Wei X, Tu YF, Zhou X. Vector Index Recall Optimization for Batch Updates. Ruan
Jian Xue Bao/Journal of Software, 2026, 37(3): 1084–1103 (in Chinese). http://www.jos.org.cn/1000-9825/7519.htm

Vector Index Recall Optimization for Batch Updates
1
1
2
1
1
2
WANG Ke , HU Si-Jie , HU Hui-Qi , ZHAO Ming-Hao , WEI Xing , TU Yao-Feng , ZHOU Xuan 1
1
(School of Data Science & Engineering, East China Normal University, Shanghai 200062, China)
2
(Zhongxing Telecommunication Equipment Corporation, Shenzhen 518057, China)
Abstract: Approximate nearest neighbor search (ANNS) is a foundational technology supporting applications such as vector databases,
recommendation systems, and large language models (LLMs). Among these, the hierarchical navigable small world (HNSW) graph
indexing technique constructs a hierarchical structure to quickly locate results within the target region, thus achieving high retrieval recall
at low computational cost. However, existing HNSW algorithms are primarily designed for static data retrieval scenarios and fail to
account for the impact of data updates on retrieval performance. Through research on real-world datasets, it is found that data in vector
databases is typically updated in batches, and their similar characteristics weaken the effectiveness of heuristic pruning in HNSW

* 基金项目: 国家重点研发计划 (2023YFC3341200); 中兴通讯产学研合作基金 (IA20250625030)
王可和胡思劼为共同第一作者.
本文由“向量数据库及 DB4LLM 技术”专题特约编辑高宏教授、李国良教授、张蓉教授推荐.
收稿时间: 2025-05-07; 修改时间: 2025-06-30, 2025-08-14; 采用时间: 2025-08-20; jos 在线出版时间: 2025-09-02
CNKI 网络首发时间: 2026-01-08