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

王嘉翼 等: 向量数据库的 K 近邻图高效更新方法 1011

然而, 当嵌入模型经过微调后, 数据点的嵌入向量会发生变化, 导致 K 近邻图中原有的邻居关系不再准确. 传统的
解决方法通常依赖于全图重建来适应这些变化, 但这一过程计算量大、效率低, 难以满足大规模应用或更加实时
的需求.
针对这一问题, 本文提出了一种高效的 K 近邻图更新方法 FastAdjust, 其系统框架如图 3 所示. FastAdjust 的
核心思想是在嵌入微调之前, 对数据进行一系列预处理以得到对向量间关联更细致的信息, 使得在嵌入模型被微
调后, 可以利用这些预处理得到的信息快速调整 K 近邻图, 从而有效适应嵌入向量的变化.

嵌入微调前预处理 嵌入微调后调整 K 近邻图
乘积量化计算 动态分配检查规模
聚类中心距离 计算每条数据 分配检查比例 K 近邻变化大的点
M 份 计算与排序 变化幅度 60 分配更多检查数量
K 近邻变化数量 40 20 根据权重:
数据变化幅度
第 i 条数据 微调前 微调后 数据密度估计
0 5 10 15 20 25
嵌入向量变化幅度与周围密度乘积
… … … …
迭代更新 K 近邻图
K 近邻密度估计
枚举邻居对 基于聚类快速过滤 更新 K 近邻图
KNN 距离 A
A 基于乘积量化结果
密度的估计: B 快速过滤距离远 过滤 B
… KNN 中后 40 个近邻 D 的点 D
第 i 条数据 … 距离的极差
C C
迭代至收敛
图 3 FastAdjust 系统框架图

在 FastAdjust 的预处理阶段, 其首先对数据进行基于乘积量化编码的处理, 借助这一信息, 在 K 近邻图更新阶
段, 能够快速为每个数据点定位距离较近的数据子集. 此外, FastAdjust 还会利用微调前 K 近邻的分布情况来估算
每个数据点周围数据的密度, 以辅助在 K 近邻图更新阶段更准确、快速地估计每个数据点 K 近邻关系的变化程度.
在嵌入模型微调后, FastAdjust 进一步利用“邻居的邻居也很可能是邻居”这一观察, 不断对 K 近邻图中的节
点采样邻居对, 通过代价较低的过滤或是实际距离计算, 判断邻居对能否成为彼此的邻居 (在下文中, 将这一过程
称作检查). 通过迭代的方式, FastAdjust 能够在嵌入微调后的向量空间上逐步更新微调前构建的 K 近邻图. 与传统
的 NN-descent 方法不同, FastAdjust 充分考虑了嵌入微调带来的细微变化特性, 从而实现更加高效的更新. 具体来
说, 下文将详细介绍 FastAdjust 使用的两个关键子策略: 候选数据定位与动态更新资源分配. 这两个子策略分别通
过避免不必要的距离计算和识别不同数据点 K 近邻变化幅度, 并以此分配更新资源, 实现优化 K 近邻图调整效率
的目标.
(1) 基于乘积量化的候选数据定位: 微调前后数据的嵌入向量变化有限, 因此微调前距离很远的嵌入向量在微
调后仍然难以形成近邻关系. 基于这一特点, FastAdjust 提出了一种基于乘积量化的候选数据定位方法, 利用预处
理阶段计算的信息, 快速定位距离较近的数据点, 并以低代价高效过滤较远的点.
(2) 基于数据密度的动态更新资源分配: 此外, FastAdjust 还依据预处理阶段计算的密度信息, 结合数据微调后
的变化程度, 为每个数据点分配不同的更新资源 (检查次数), 从而实现更高效、更精准的 K 近邻图更新.
通过这种高效的 K 近邻图调整策略, FastAdjust 能够避免全图重建的巨大开销, 在嵌入微调后迅速调整图结
构, 从而有效减少嵌入模型微调对 K 近邻图结构造成的影响.
3.2 基于乘积量化的候选数据定位
在模型微调的场景中, 一个显著的特点是微调对每个数据点的影响一般是有限的, 也就是数据嵌入的变化幅
度较小. 因此, 微调后数据点的嵌入向量变化及其邻居变化通常是局部性的: 微调后某个数据点的新邻居往往是其
微调前距离较近的点. 基于这一观察, 为了避免全局搜索带来的高计算开销, 我们可以在调整 K 近邻图时, 重点关