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

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

具有树状的层次结构并通过基于表的方法进行存储, 实现了对树上非连续节点的并行计算. 此外, GTS 设计了一
种并发搜索策略以预防内存死锁, 并引入一个成本模型以平衡并发与剪枝效率. BANG [129] 研究如何在显存受限的
情况下通过单 GPU 处理大量数据. BANG 利用 CPU 与内存处理索引与数据, 并利用 GPU 加速距离计算, 还通过
阶段性执行策略优化了 GPU-CPU 的负载均衡. CAGRA [130] 面向英伟达 GPU 设计了基于图的近似最近邻搜索算
法. 实验结果显示, 相较于 CPU 上的方法, CAGRA 性能获得了大幅提升.
3.2 面向学习增强的优化
人工智能技术已经被广泛用于优化数据库性能, 其中学习型索引近年来取得了很大的进展. 学习型索引的核
心思想是通过学习数据的分布来优化索引结构和查询过程, 从而提高系统的性能. 当前有很多工作利用学习的方
法来优化高维向量近似最近邻搜索的性能, 通过采用学习的方法, 能够充分挖掘高维向量的分布特征, 从而有针对
性地优化算法. 当前利用学习的方法来优化高维向量索引主要是为了能够基于数据的分布来更好地划分数据, 从
而能够使查询更高效、准确地定位到邻近点所在区域, 减少数据的访问开销. 下面我们介绍相关的技术方案.
(1) Neural LSH 索引
文献 [103] 提出的 Neural LSH 方法利用神经网络将数据更好地划分到多个桶中. 传统的利用聚类、LSH 以
及树的方法难以捕捉到数据的分布特征. Neural LSH 通过神经网络来学习数据的分布特征. 它利用图划分技术和
有监督学习的方法来优化数据的划分, 图 8 展示了其划分示意图. 该方法主要分为 3 个重要的步骤: (1) 构建一个
KNN 图, 利用 KNN 图来捕捉数据的分布特征; (2) 利用平衡图划分技术将数据均匀地划分到多个桶中; (3) 训练一
个基于神经网络的分类器, 将其应用到整个数据空间, 对所有的数据进行划分. 为了提升划分的效果, 该方法采用
层次化的划分结构, 逐层递归地划分子空间, 先划分为大的区域, 然后对每个区间做进一步的划分. 实验结果表明,
在通过 Neural LSH 划分的数据上进行搜索能够取得优于传统的聚类方法和 LSH 方法的性能.

BIN 1
R 1
R 0

R 2
BIN 2

图 8 Neural LSH 划分示意图

(2) BLISS 索引
BLISS [104] 采用迭代的方式来优化数据的划分, 通过交替进行以下两个步骤来优化分区: (1) 通过学习将数据映
射到对应的桶; (2) 以每个桶中数据均衡为目标重新分配数据点. 在训练映射函数阶段针对每个数据点会学习到针
对桶的评分函数, 并每次在评分最高的 K 个桶中选择负载最小的桶来进行分配, 总共训练 R 个映射函数. 在推理
阶段, BLISS 通过 R 个已训练好的映射函数对数据点进行映射, 每个映射函数分别选择 5 个桶来获取候选结果, 在
这些候选结果中进一步筛选以获取最后的查询结果. 实验结果表明, BLISS 在多个数据集上都取得了优于 Neural
LSH 的性能.
(3) BATL 索引
BATL [131] 是一个基于平衡 K 叉树的学习型层次划分索引, 同一个桶中的数据被一条从根节点到叶子节点
的路径表示, 查询过程是从根节点不断路由到叶子节点的过程. 其将路由任务转化为分支序列生成任务, 利用
Transformer 模型 [132] 设计了一个解码器编码器框架, 在搜索时利用这个框架和束搜索 (beam search) 来生成分支序
列, 动态地将查询从根节点路由到叶子节点. BATL 的训练过程首先随机初始化一棵平衡树, 然后随机选择部分数
据点作为查询点, 根据当前的树结构生成 (查询, 路径) 对作为训练数据, 将任务建模为自回归分类问题, 采用序列
到序列的学习范式进行训练. 其整个训练过程是交替迭代的, 固定树结构, 训练路由模型; 固定路由模型, 更新树结