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

990 软件学报 2026 年第 37 卷第 3 期

构, 逐渐完成整个训练过程. BATL 训练多个树模型以提高召回率, 实验展示出其在时延、准确性和内存占用之间
取得了良好的平衡.
(4) LIDER 索引
LIDER [133] 是一个基于聚类的双层层次结构的学习型索引. 它包括两个重要的组成部分, 第 1 层维护了聚类的
中心点, 第 2 层维护了聚簇数据. 在这两层中, 都包含一个称为 core model 的组件, 其包含两个部分: (1) 降维模块;
(2) 一个位置预测模块 RMI. 降维模块又分为两个部分, EK-LSH 用来将数据映射成哈希键, 键重缩放组件用来将
字符类型的哈希键映射到数值型, 用于 RMI 模块的训练. LIDER 的整体工作流程是: 首先将数据利用 K-means 聚
类, 然后对聚类中心点和每个聚类都训练对应的 core model, 最后将所有的 core model 组合成一个索引. 在搜索阶
段, 查询首先搜索到对应的聚类中心点确定要搜索的聚类, 然后在对应的聚类中进行搜索, 多个聚类采用并行的方
式进行搜索, 最后将来自每个聚类的结果合并, 取前 k 个结果返回. 实验结果表明, LIDER 与已有的索引相比, 在取
得更高搜索速度的同时具有更高的召回率.
表 7 对比展示了上述 4 个方法. 此外, 文献 [134] 利用梯度下降树学习到提前终止搜索策略, 以用于在向量搜
索的过程中提前终止从而减少冗余搜索. 文献 [135] 提出一个基于编码解码器的方案 PCE-Net 来确定需要参与搜
索的倒排列表的数量, RPQ [136] 为基于图的方法设计了一种路由指导的端到端的学习型乘积量化方法, 其通过采样
并提取出路由特征与近邻特征用于训练多个可微的量化器, 使得量化结果更好地适应基于图的近似最近邻搜索.
文献 [137] 提出利用学习的方法来设计面向磁盘的 I/O 优化的方法. 它通过学习的方法来使投影后点的相对顺序
和原始高维空间尽可能一致从而减少随机访问. SmartANNS [138] 利用学习的方法来确定需要搜索的数据分片所在
的 SmartSSD 来实现更高的设备利用率.

表 7 4 个学习增强方法的对比

索引技术 核心思想 组织形式 技术特点 优点 缺点
利用神经网络学习数据分布, 结 递归划分数据形 有监督学习、图 优于传统LSH和聚 训练开销大, 层级
Neural LSH
合图划分技术优化数据分层划分 成多层桶结构 划分技术结合 类方法的搜索性能 划分可能引入误差
优于Neural LSH的 映射函数数量影响
迭代优化数据划分: 交替训练映 多映射函数+负 迭代式负载均衡
BLISS 性能, 索引的空间 性能, 候选桶筛选
射函数与数据重分配 载均衡桶 策略
占用比HNSW低 计算复杂
将路由任务建模为序列生成问 训练需反复迭代树
BATL 题, 基于Transformer的编解码框 平衡K叉树 树结构+自回归 树与Transformer进 结构, 模型复杂度
序列学习
行结合, 技术新颖
架动态构建平衡K叉树 较高
聚类中心层+聚
基于聚类的双层结构 (中心点+聚 降维技术与聚类 聚类中心质量依赖
LIDER 簇数据层的双层 并行友好
簇), 结合降维与位置预测模块 结合 初始K-means
结构

3.3 面向距离比较操作的优化
在向量搜索中, 计算代价在性能开销中占据了很大比重, 其主要是由在搜索的过程中计算两个点的距离产生
的, 通过优化计算代价可以提升系统的性能. 文献 [105] 中提出, 在搜索过程中涉及共同的一个关键步骤, 比较两
τ
个点之间的距离是否小于一个阈值 τ, 如果小于 , 则返回两个点之间的距离, 这个过程被称为距离比较操作
(distance comparison operation, DCO), 距离计算操作主要发生在这个过程中. 为了完成这个操作, 基本方法是计算
两个点之间的距离, 然后判断是否小于 τ. 文献 [105] 指出, 对于大部分的点, 两个点之间的距离都是大于 τ 的, 不
τ 即可, 这带来了优化距离计算的机会. 如图 9 所示, 仅计算部分距离
需要计算其真实距离, 只需要判断是否小于
并与阈值比较, 在不满足要求的情况下及时终止距离计算, 从而优化计算代价.
ADSampling [105] 提出利用假设检验的方法来估计距离是否大于 τ, 其核心是采用随机投影的方式将数据投影
τ. 这是一个迭代的过程, 通过不断
到子空间, 估计两个点的距离, 然后通过假设检验判断两个点的距离是否大于
采样更多的维度来优化估计的精度直到点被过滤或者真实距离被计算出来. 实验结果显示, 将这一方法应用于
HNSW 和 IVF 索引后减少了距离计算, 进而提高了搜索性能. DDC [139] 在 ADSampling 的基础上, 将随机投影改成