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

宋子文 等: 向量数据库中近似最近邻搜索关键技术综述 977

HNSW 的设计理念为后续图方法研究和改进提供了重要启示. FANNG [44] 是和 HNSW 同期提出来的图构建算
法, 除了与 HNSW 相同的邻居构建策略外, 还进一步引入了阈值 τ 来选择更多的候选邻居节点. NSG 图是一个单
层图结构. 它形式化地描述了单调搜索网络 [17] , 并依此提出了 MRNG (monotonic relative neighborhood graph), 在
构建图的过程中, 其邻居节点选择策略与 HNSW 一致. SSG [45] 在 NSG 的基础上进一步改进, 使每个节点的邻居节
点在不同方向上尽可能均匀地分布. HSSG [46] 进一步提出了多层结构以加快搜索速度. DPG [10] 在 KNN 图的基础上,
在节点选择过程中引入邻居节点之间角度的信息以使节点更分散, 从而提升搜索性能. 针对 NSG 等图的构建策略
会导致搜索路径太长的问题, Vamana 图 [36] 提出在构建阶段引入一个参数 α 来调节裁边选点力度的 α-RNG 规则,
∗
p
将所有的候选邻居节点按照与将要建立邻居的点 p 的距离升序排列, 对于当前准备要与 p 建立邻居的 , 如果满
′
∗ ′ ∗ p 为已经建立的邻居节点. Vamana 采用两阶段迭代的图构建策略: 首
足 α∥p −p ∥ ⩽ ∥p −p∥, 则不作为邻居, 其中
先生成随机图结构, 随后对每个节点执行贪婪搜索以确定潜在邻居集合, 并通过鲁棒剪枝 (RobustPrune)
α 的邻居. 具体而言, 剪枝过程会保留对搜索方向贡献最大的邻居, 同时剔除冗余连接, 从而
筛选出满足距离约束
降低图直径并减少搜索时的跳数. τ-MG 指出 [43] , MRNG 的方法都基于查询点 q 是数据集中的一点这一假设来设
计, 但实际中往往并非如此, 对于查询点不存在于数据集中的情况, 在 MRNG 图中搜索会出现无法发现最近邻点
的情况, 基于此观察提出了 τ-MG 的选点策略, 使查询 q 和近邻点 p 在满足 δ(q,p) < τ 的情况下依然能够搜索最近
邻. 图 1 基于文献 [43] 的描述进一步调整优化, 展示了这两个方法的选点策略, 可以看到, τ-MG 降低了某个点成
为邻居节点的要求. HNSW 通过将数据点不断插入图中最终完成索引构建的增量方式可以支持动态数据的插入,
避免面对增量数据时进行索引的全局重建. NSG 等方法主要针对的是静态数据集, 在完整的数据集上完成最终的
图构建. 它们依赖于先构建一个基础的近邻图, 然后在此图上针对每个节点运行贪心搜索策略来确定候选集, 并利
用相应的选边策略来确定最终的邻居节点, 如 NSG 依赖于先构建一个近似 K 近邻图 (KNN graph), 而 τ-MG 依赖
于先构建一个 NSG 或者 HNSW 图.
在 DEEP、SIFT、MSong、GIST、CRAWL、GloVe 这 6 个经典数据集的对比上, 根据文献 [43], 在相同召回
率下, τ-MG 可以取得比 NSG 更好的搜索性能, 而 NSG 取得了优于 HNSW 的搜索性能. 表 4 展示了这 6 个数据集
的统计信息.

表 4 6 个主要数据集的统计信息

数据集 维度 数据量 查询数量 类型
DEEP 256 1 000 000 200 图片
SIFT 128 1 000 000 10 000 图片
MSong 420 990 000 200 音频
GIST 960 1 000 000 1 000 图片
CRAWL 300 1 980 000 10 000 文本
GloVe 100 1 180 000 10 000 文本

此外, HCNNG [47] 基于分治的思想来构建图. 它将数据集递归地依据每次随机选择两个数据点进行二分类, 直
到每个子集中的数据点个数小于预定义的数量 N 时则停止划分, 然后分别针对每个子集分别构建最小生成树, 最
后将每个子集进行合并. 这个递归划分并合并的过程会进行多次, 最后将多次形成的图进行合并以形成最终结果.
HCNNG 不依赖贪心搜索策略来获取候选集, 而是依赖于将数据集划分为多个子集, 同时其连边策略依赖于在这
些子集中构建最小生成树. 实验展示其在 GIST、SIFT 等经典数据集上取得了优于 HNSW 的搜索性能. RoarGraph [48]
研究跨模态的近似最近邻查询. 由于不同模态的数据通过嵌入生成的向量属于不同分布, 使得查询向量相较于数
据集中的向量出现分布外 (out-of-distribution) 的情况. 针对这类问题, RoarGraph 提出了一种查询导向的图索引方
法, 通过二分图来建模维护跨模态数据间的距离度量.
2.1.2 更新策略
传统基于图的近似最近邻索引 (如 HNSW、NSG 等) 虽然在静态数据集上表现出色, 但是其静态特性无法应