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

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

CPU 下, HNSW 索引在 GIST 和 DEEP 数据集上不使用 SIMD 加速和使用 SIMD512 指令集进行加速的查询性能
(QPS), 可以看出, 通过开启 SIMD 来加速距离计算, 可以获得最多 2.6 倍的性能提升.

表 6 HNSW 在开启 SIMD 和不开启 SIMD 时查询性能 (QPS) 对比

96%召回率 98%召回率
SIMD加速状态
DEEP GIST MSong DEEP GIST MSong
NonSIMD 542 87 1 375 407 54 1 067
SIMD 1 291 (2.3×) 227 (2.6×) 2 518 (1.8×) 886 (2.1×) 141 (2.6×) 1814 (1.7×)

3.1.2 利用多线程的优化方法
并行设计已经普遍应用在计算机系统中, 通过利用 CPU 的并行能力, 同时执行多个操作来提升性能. 当前多
线程的加速可以分为两类: 多线程构建和多线程查询加速. 构建的多线程是将数据集划分为多个子集, 然后在多个
线程中并行执行插入操作, 最后将所有的结果进行合并来得到最终的结果. 查询的多线程是将查询操作分为多个
子任务, 然后在多个线程中并行执行, 最后将所有的结果进行合并来得到最终的结果.
(1) 构建的多线程优化
基于图的方法已经广泛应用在向量数据库中. 图的构建是一项十分耗时的任务, 通过并行技术来加速图的构
建是一个可行的方案. 当前 HNSW 图的构建是将所有数据点按照一定顺序插入图中, 当插入点 p 时, 算法在 p 和
图中的现有点之间添加新的边, 其依赖算法 1 在当前图中搜索获取相应的候选点, 然后执行对应的选点操作完成
邻居节点的构建. 文献 [119] 提出了一种基于多线程的图构建方法, 利用多线程来加速图的构建过程. 其主要思想
是将数据集分为多个批次, 在每个批次上执行多线程插入操作, 同时确定多个点的邻居节点.
具体来说, 采用指数级批量增加方法来逐渐增加每个批次的点的数量. 初始状态, 每个批次的点的数量较少,
这更类似于顺序版本, 从而允许更高质量的图, 后续随着图变得更大, 允许一批中有更多的数据点, 从而实现更高
的并行度, 同时, 对批的大小设置一个上限避免无限增大. 通过这种方法, 实现了在性能和图的质量之间的平衡. 在
对每个点构建邻居节点的过程中, 第 1 步是确定其邻居节点 (出边), 第 2 步是确定 p 是否可以作为这些节点的邻
居 (入边). 对于前者, 批处理中的所有数据点在不可变快照上独立构建自己的邻域, 因此不会相互影响. 对于后者,
会收集当前批次在第 1 步添加的出边, 然后统一对出边指向的节点执行选点操作来确定入边, 从而实现无锁的并
行入边构建.
(2) 搜索的多线程优化
多线程同样可以用来加速搜索过程. 利用多线程的一个基本方案是, 对于多个查询同时到来的情况, 并发地执
行多个查询. iQAN [120] 是一个利用多线程来加速单个查询的性能的方法. 基于图的方法是在图上不断地遍历数据
点的过程, iQAN 的核心思想是并行地在图上检查数据点, 通过同时搜索多个路径上的点, 实现同时对多个范围内
的数据进行检查, 然后将检查的结果合并, 在合并结果的基础上进行新的多个范围的检查. 主要搜索策略包括: (1)
路径并行, 通过多个线程同时搜索多个不同的路径实现并行搜索; (2) 分阶段扩展, 随着搜索的进行, 逐步扩展线程
数量, 用更多的路径来实现并行搜索, 在减少起步阶段的开销的同时提高后期的遍历效率; (3) 减少同步开销, 允许
不同的工作线程检查重复的点, 避免了线程之间的同步开销, 在合并时统一进行结果去重操作. 在这些设计的基础
上, iQAN 最终实现了利用多线程来加速搜索过程, 提升了搜索性能, 在 SIFT1B 和 DEEP1B 数据集上实现了最多
16 倍的性能提升.
3.1.3 利用 GPU 进行加速
基于 CPU 的近似最近邻搜索方案面临着高维向量密集计算代价高、实时性能要求高、维护开销大的问题.
GPU 可以凭借大规模并行架构和高内存带宽的优势突破性能瓶颈, 如其可以批量计算向量之间的距离, 实现高效
的图构建等, 当前有很多工作研究如何利用 GPU 来优化近似最近邻搜索.
SONG [121] 是一个基于 GPU 加速的近似最近邻搜索系统. 该系统针对基于图的方法进行了深度优化, 首次实现
了基于图的 GPU 向量搜索框架. SONG 将搜索过程解耦为 3 个阶段: 候选定位 (candidates locating)、批量距离计算