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

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

相较于每次计算实际距离, 该算法通过代价低的判断, 快速过滤掉和目标点距离较远的点. 其过滤流程又分为
两个层级, 首先, 对于每一个 PQ 编码都是离目标点编码前 λ 近的点, 需要计算实际距离, 因为其与目标点的距离
大概率比较小. 对于不符合此条件的点, 算法通过乘积量化的近似距离计算, 快速估计其与目标点的距离. 如果近
似距离较大 (与目标点的第 K 近距离的差距大于 θ), 则将其过滤掉, 不计算其与目标点的实际距离; 否则按照估计
的近似距离, 以一定的概率进行实际距离计算. 这一概率随估计距离的增大而减小, 保证了优先检查离目标点更近
的数据.
● 示例说明. 如图 4 所示, 采用本文提出的方法后, 具有不同 PQ 编码的数据会按照不同的比例被检查 (计算
实际距离). 例如, 图中深蓝色区域离目标点较近, 由于其 PQ 编码对应的每一个聚类中心都离目标点前 λ 近, 因此
所有该区域的采样点都会与目标点计算实际距离. 对于浅蓝色区域, 其中的数据按照与目标点的距离, 以不同的概
率被检查, 而距离目标点较远的白色区域则被直接排除. 图 4 的例子表明本文提出的方法能够高效又准确地识别
出与目标点距离较近的区域, 从而准确地缩小候选范围, 有效避免计算较远数据点的实际距离, 显著提高 K 近邻
图的更新效率.

目标点

采样数据点
被检查的概率
0 100%
图 4 嵌入空间不同部分采样点的检查概率

3.3 基于数据密度的动态更新资源分配
经过微调后, 不同数据点的邻居关系变化程度有所不同. 因此, 为了提高 K 近邻图的更新效率, 不应该均匀分
配对每个点检查候选点的次数, 而应根据邻居关系变化的程度进行有针对性的分配. 这种方法能够在较短时间内
显著提升 K 近邻图的质量. 然而, 邻居关系变化程度是一个依赖于微调后的 K 近邻图、只有在图更新后才能准确
计算的变量. 为了解决这一问题, 我们需要探索与邻居关系变化幅度相关性较高的其他变量, 通过这些变量来替代
邻居关系的直接计算, 从而指导节点间检查次数的分配.
直观来看, 嵌入向量本身在微调前后的变化幅度和数据点周围的数据密度是两个影响邻居关系变化幅度的关
键因素. 本身嵌入向量变化较大的点, 其邻居关系通常会发生较大的变化. 而在数据密集的区域, 数据点间的邻居
关系对嵌入向量的微小变化更加敏感. 因此, 即使嵌入向量发生较小的变化, 也可能对邻居关系产生显著影响. 例
如, 图 5 中微调后嵌入向量变化较大的数据点, 它们的邻居关系通常发生了显著变化. 而在低密度区域, 即使嵌入
向量发生较大变化, 邻居关系却几乎未发生变化. 例如, 图中蓝色点的周围数据稀疏, 与蓝色点之间距离的差异较
大, 因此即便其嵌入向量发生了较大的变化, 邻居关系变化也较小 (如其 3 个近邻在微调前后并无变化). 相反, 在
高密度区域 (如图中的红色点), 由于其周围数据较为密集, 与红色点之间距离的差异较小, 即便嵌入向量变化较
小, 也可能导致邻居关系的显著变化 (如红色点的 3 个近邻中有 2 个发生了变化).

嵌入向量 嵌入向量
嵌入模型
微调

高密度区域 低密度区域
图 5 不同密度区域 K 近邻关系变化情况的示例