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

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

*
向量数据库的 K 近邻图高效更新方法

王嘉翼, 徐士惠, 李国良

(清华大学 计算机科学与技术系, 北京 100084)
通信作者: 李国良, E-mail: liguoliang@tsinghua.edu.cn

摘 要: 在高维数据处理中, K 近邻图作为一种关键的数据结构, 广泛应用于聚类、图神经网络和推荐系统等领域.
然而, 随着预训练嵌入模型在非结构化数据建模与检索中的广泛使用, 嵌入模型的微调逐渐成为提升嵌入向量的
语义表示能力的核心步骤. 嵌入微调通常会导致全部数据的向量表示发生系统性变化, 从而使原有 K 近邻图的邻
接关系失效. 现有研究主要关注于如何为静态数据构建 K 近邻图, 缺乏对微调后的嵌入向量进行快速适应的研究.
为此, 提出一种面向嵌入模型微调场景的高效 K 近邻图更新方法 FastAdjust. 该方法基于嵌入模型微调为每条数据
嵌入带来的影响较小的观察, 通过局部更新策略对原始 K 近邻图进行增量调整, 在确保最终 K 近邻图质量的同时,
显著提升更新效率. 具体而言, 首先, FastAdjust 利用基于乘积量化的聚类结构, 为每条数据高效且准确地定位可能
成为邻居的数据子集, 缩小候选邻居搜索范围; 其次, 基于数据密度和嵌入变化幅度, FastAdjust 结合二者与数据
K 近邻变化程度的相关性, 为邻居关系变化程度不同的数据针对性地分配不同的更新资源, 从而提升整体更新效
率. 真实数据集上的实验结果表明, FastAdjust 在嵌入模型微调的场景下能够快速调整 K 近邻图, 准确地适应数据
嵌入的变化, 同时大幅减少计算开销, 具有良好的实用价值和扩展性.
关键词: K 近邻图; 近似最近邻搜索; 嵌入模型
中图法分类号: TP311

中文引用格式: 王嘉翼, 徐士惠, 李国良. 向量数据库的K近邻图高效更新方法. 软件学报, 2026, 37(3): 1006–1020. http://www.jos.
org.cn/1000-9825/7517.htm
英文引用格式: Wang JY, Xu SH, Li GL. Efficient Updating Method for K-nearest Neighbor Graph in Vector Databases. Ruan Jian
Xue Bao/Journal of Software, 2026, 37(3): 1006–1020 (in Chinese). http://www.jos.org.cn/1000-9825/7517.htm

Efficient Updating Method for K-nearest Neighbor Graph in Vector Databases

WANG Jia-Yi, XU Shi-Hui, LI Guo-Liang
(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

Abstract: In high-dimensional data processing, the K-nearest neighbor (KNN) graph is a critical data structure widely used in tasks such
as clustering, graph neural networks, and recommendation systems. However, with the increasing use of pretrained embedding models in
unstructured data modeling and retrieval, embedding model fine-tuning has become a key step in enhancing the semantic representation
capability of embeddings. Such fine-tuning often leads to systematic changes in the vector representations of all data points, which
invalidates the original neighborhood relationships in the KNN graph. Existing research primarily focuses on building KNN graphs for
static data, lacking efficient solutions for adapting to updated embeddings after fine-tuning. To address this gap, this study proposes
FastAdjust, an efficient KNN graph update method tailored for embedding model fine-tuning scenarios. Leveraging the observation that
fine-tuning usually causes only minor changes to individual embeddings, incremental adjustments to the original KNN graph are performed

* 基金项目: 国家重点研发计划 (2023YFB4503600); 国家自然科学基金 (62525202, 62232009); 深圳市承接国家重大科技项目
(CJGJZD20230724093403007); 高速铁路与城轨交通系统技术国家工程研究中心实验室基础研究项目&中国国家铁路集团有限公司科
技研究开发计划 (L2024W001)
本文由“向量数据库及 DB4LLM 技术”专题特约编辑高宏教授、李国良教授、张蓉教授推荐.
收稿时间: 2025-05-06; 修改时间: 2025-06-30; 采用时间: 2025-08-20; jos 在线出版时间: 2025-09-02
CNKI 网络首发时间: 2026-01-15