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

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

实验结果如图 9 所示. 从实验结果可以看出, FastAdjust 的 RMSE 显著低于其他基线方法. 由此, 本文从召回
率以外的另一个角度, 证明了 FastAdjust 能够快速调整 K 近邻图的结构, 在很短的调整时间内取得与真实 K 近邻
图相似的图结构, 使其适应嵌入模型微调对 K 近邻图产生的结构性变化.

Stale NN-descent NN-descent-init FastAdjust
50
45.9
10.4
入度的均方根误差 (RMSE) 5 7.5 入度的均方根差误差 (RMSE) 30 16.9
40
9.8
10
20

3.0
9.1
10
2.5
0 0
(a) Stack (b) DigiFace
图 9 不同方法更新 K 近邻图, 3 min 后节点入度均方根误差的比较

4.5 不同参数与 K 近邻变化个数的相关性
为了验证第 3.3 节中所提出的基于数据密度的动态更新资源分配的合理性, 本节评估了不同变量与数据 K 近
邻微调前后变化个数的相关系数, 结果如表 2 所示.

表 2 不同变量与 K 近邻变化个数的相关系数

变量 Stack Wiki
位移距离 0.411 0.391
/
1 (前100近邻的平均距离) −0.365 −0.367
/
1 (前100近邻距离的极差) 0.223 0.203
/
1 (前100近邻中后40近邻距离的极差) 0.564 0.575
/
(位移距离) (前100近邻的平均距离) −0.071 −0.182
/
(位移距离) (前100近邻距离的极差) 0.332 0.278
/
(位移距离) (前100近邻中后40近邻距离的极差) 0.649 0.636

从表 2 中相关系数的结果可以看出, 不同变量对 K 近邻变化个数的影响存在一定的规律, 这些关系为我们提
供了对 K 近邻结构变化的深入理解. 微调前后数据位移距离 (即数据变化幅度) 与 K 近邻变化个数之间的相关系
数为正 (例如, Stack 和 Wiki 上的相关系数分别为 0.411 和 0.391), 说明当位移距离增大时, K 近邻的变化个数也倾
向于增加. 这表明, 数据微调后较大的位移可能导致 K 近邻结构发生较大的调整. 前 100 近邻中后 40 近邻距离的
极差同样与 K 近邻的变化个数显示出较强的正相关 (如 Stack 和 Wiki 分别为 0.564 和 0.575), 说明前 100 近邻中
后 40 近邻的距离差异对 K 近邻变化个数有较大影响. 位移距离/前 100 近邻中后 40 近邻距离的极差是与 K 近邻
变化个数相关系数最高的变量 (Stack 和 Wiki 分别为 0.649 和 0.636). 这表明这一变量与 K 近邻的变化有较强的
正相关性. 当这个比值较大时, K 近邻的变化个数一般也显著增加, 因此, 通过基于该变量的取值为每条数据动态
分配更新资源, 也就是分配不同的检查次数, 可以提高对计算资源的利用效率, 为 K 近邻变化较大的数据分配更
多资源来调整其邻居关系, 从而加速整个 K 近邻图的调整.
通过分析不同变量与 K 近邻变化个数的相关系数, 我们发现, 数据点的位移距离和近邻距离的差异程度对微
调前后 K 近邻变化的程度有重要影响. 这些结果支持了第 3.3 节提出的基于数据密度的动态分配更新资源的合理
性. 未来的研究可以进一步探讨这些变量在实际应用中的具体影响, 以优化 K 近邻图更新算法在不同数据分布下
的表现.