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

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

通过在文本及图像的真实数据集上实验, 从 K 近邻图的准确度和更新的时间效率这两个方面全面验证本方法的
有效性. 第 5 节总结全文, 并介绍未来工作.

1 相关工作

1.1 高效的 K 近邻图构建算法
K 近邻图是一种广泛应用于高维数据处理中的基础结构, 常用于聚类、图神经网络、图嵌入、推荐系统、图
搜索等任务中 [6] . 其基本思想是: 对于数据集中每一个样本点, 寻找与之距离最近的 K 个邻居, 并以此建立有向或无
[7]
[8]
向图结构 . 在实际应用中, 由于数据量巨大、维度较高, 如何高效、准确地构建 K 近邻图是一个重要的研究问题 .
目前已有多种用于构建 K 近邻图的算法被提出, 其中也包含用于近似最近邻查找的索引, 因为可以在近似最
近邻索引建立后, 通过为每一条数据查询近似的 K 近邻来构建 K 近邻图. 这些方法主要可分为以下几类.
● 暴力搜索. 暴力搜索是最直观和精确的构建 K 近邻图的方法. 它通过计算所有点对之间的距离, 从中选取每
个点距离最近的 K 个点作为其邻居, 并通常采用欧氏距离、余弦距离等度量方式. 该方法能获得最精确的 K 近邻
图, 构图质量最优, 但时间复杂度高, 在大规模数据上难以应用, 且无法扩展到动态更新或流数据的场景.
[9]
● 基于树结构的方法. 其基本原理是通过构建空间划分树 (如 KD-Tree ) 对数据进行递归划分, 使得 KNN 查
询时仅需遍历部分节点, 从而加快近邻搜索效率. Wang 等人 [10] 采用分治方法将点递归划分为子集, 形成随机划分
树, 并在每个子集上构建精确邻域图, 通过邻域传播方法提高准确性. 这类方法在低维数据中性能优异, 能显著提
升查询效率, 但在高维空间中空间划分效果变差, 导致这类方法退化为近似于线性扫描的过程. 同时, 该方法构建
树结构的过程也需要较多时间和较大空间.
● 图增量构建方法. 这类方法先随机为每个点选择 K 个邻居来构建初始的邻接图, 再通过局部搜索或图遍历
迭代优化邻居列表. Dong 等人 [11] 提出了 NN-Descent 方法, 该方法先随机初始化每个点的邻居集合, 然后利用“邻
居的邻居也是可能的邻居”原则, 通过迭代地检查邻居和邻居之间的距离, 逐步优化邻接关系. Malkov 等人 [12] 提出
了 HNSW 方法, 引入分层图结构, 从上层粗粒度搜索到下层精细搜索, 加速图的构建过程并提升查询准确性. 图增
量构建方法在高维、大规模数据场景下表现出较好的效率与精度平衡, 且具有较好的可扩展性, 部分方法支持一
定程度的动态更新, 适用于在线场景, 因此已成为主流方案. 然而, 这类方法的问题主要在于: 近似算法构建结果非
最优, 可能影响后续任务精度; 算法的超参数 (如迭代轮数、邻接个数) 较多, 调节参数的过程复杂; 构图过程涉及
随机性, 效果可能存在波动.
● 基于哈希和量化的方法. 这类方法借助局部敏感哈希 (locality sensitive hashing, LSH)、乘积量化 (product
quantization, PQ) [19,20] 等技术进行高效近似 K 近邻索引构建, 批量进行 K 近邻查询, 再合并结果构建 K 近邻图.
Faiss (Facebook AI similarity search) 支持多种索引类型, 并结合 GPU 加速. 这类方法构图效率高, 适合处理千万级
以上样本, 适用于大规模的工业级应用, 但构图结果的精度受限于索引结构和参数设置. 某些方法 (如量化) 可能
对语义空间造成破坏.
1.2 K 近邻图更新方法
在 K 近邻图构建之后, 如果数据发生变化 (如新增点、删除点或已有点的特征发生更新), 完全重建 K 近邻图
代价较高. 因此, 研究者提出了 K 近邻图的增量更新方法.
对于新增点的插入更新, 当一个新样本加入时, 无须重建整个图, 可以通过以下方式更新: 使用现有 K 近邻图
(或其索引结构) 对新点进行 K 近邻查询, 根据距离条件将该新点作为邻居加入这些近邻的邻接列表中, 并将其自
身的邻接列表设置为查到的 K 个点. 在初始插入后, 可采用若干轮局部迭代进一步修正新点及其邻居的邻接关系,
提升图结构质量. 例如, Malkov 等人 [12] 提出的 HNSW 方法支持基于上述方法动态添加节点. 此外, 另一类常用的
支持数据点的插入操作的方法 [14–16] 是动态建立一个辅助索引, 专门存储新增的数据点, 并阶段性地将辅助索引与
全局的向量索引进行合并. Xu 等人 [17] 提出了基于倒排索引的索引原地更新策略, 用来避免维护辅助索引及定期更
新全局索引的计算开销以及不均衡的计算负载. 然而这些方法只适用于插入数据的情况, 当全量数据的嵌入向量