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

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

multiple data) 指令加速距离计算. 更多关于量化的内容可以参考文献 [15].
2.4.2 标量量化
标量量化是一种广泛应用于向量压缩的技术 [89] , 旨在通过降低数据精度来减小存储和计算开销, 其核心是将
高维向量的每个分量的连续浮点数映射到有限个离散值, 从而用更少的比特来表示数据. 例如, 将 32 位的浮点数
量化为 8 位的整数, 可以将存储需求减少为原来的 1/4. 标量量化的优势不仅体现在存储压缩上, 还体现在加速相
似性搜索过程, 由于数据量变小, 搜索过程中能够更快地访问内容, 进而提高搜索速度.
标量量化的基本步骤如下. (1) 确定量化范围. 分析数据的分布情况, 如浮点向量的最大值、最小值, 以确定量
化区间的上下界. (2) 划分量化区间. 根据目标精度和存储需求, 划分为若干个离散值区间. (3) 映射. 将每个浮点数
映射到对应的离散值, 通常采用线性映射或非线性映射. (4) 存储. 保存量化所需要的元数据, 包括上下界、步长、
码本等内容, 以便在搜索时能够还原为近似的值. 标量量化的关键在于如何选择离散值和映射方式, 以最小化量化
误差和存储开销. LVQ (locally-adaptive vector quantization) [35] 是一个局部自适应的量化方法. 它考虑每个向量的特
点来有针对性地优化, 并提出两层量化机制来对残差部分进一步量化从而提高精度. 后续将详细介绍 LVQ.
RaBitQ [34] 是一种新型的量化方法. 它利用乘积量化和标量量化的优点, 取得了显著的效果. 不同于传统的乘积
量化方法, 它提供了误差界限的理论保证. 它将 d 维的向量量化为 d 比特的二进制编码, 并设计无偏估计方法来计
算向量间的内积. 为了能够高效地进行计算, RaBitQ 引入了标量量化, 将查询点进行标量量化之后参与计算, 通过
这一操作, 在计算中引入了位运算, 从而能够加快计算速度. 文献 [34] 中提供了两种方法, 一种针对的是单条量化
数据的计算, 另一种是针对批量量化数据的计算. 前者通过比特级别的操作 bitwise-and 结合 popcount 实现快速计
算, 而后者则是通过结合 SIMD 指令集的查表操作来实现快速计算. 文献 [34] 将 RaBitQ 应用在 IVF 索引结构中
以优化近似最近邻搜索的速度, 实验结果表明其能够获得比传统量化更快的查询速度. 文献 [90] 针对 RaBitQ 只
支持 1 比特量化的问题, 进一步扩展了 RaBitQ 的支持范围, 使其能够选择较小的压缩率来实现增加空间占用, 从
而获得更高的估计精度, 同时保留了对距离的无偏估计能力.
2.5 混合数据组织方法
结合各类数据组织方案的优点形成混合组织方案的方法受到越来越广泛的关注, 有很多研究成果展示出通过
有机的组合形成新的组织方法, 相较于单一方案能够取得更好的效果. 单一的组织方案各具优势和劣势, 通过组合
的方式可以充分发挥各个方案的优势, 同时弥补单一方案的劣势, 进而提高近似最近邻搜索效率. 下面我们介绍相
关的技术.
2.5.1 基于图和量化的组织方法
针对图能够实现高性能查询和量化可以降低内存占用的优势, Aguerrebere 等人 [35] 提出了基于图和量化的
OG-LVQ 方法, 取得了突破性的性能提升, 为处理 10 亿级高维向量相似性搜索提供了高性能解决方案. 该方法从
软件算法和硬件架构两方面进行设计.
在软件算法方面,提出了局部自适应量化的方法. (1) 该方法基于对深度学习时代高维向量分布特性的深度洞
察, 通过全局均值中心化消除维度间分布偏移后, 采用向量级动态范围标量量化策略, 使每个向量的数值范围独立
适配其统计特性, 最大化利用有限比特位的表达能力. 与传统的全局量化或分块量化 (如 PQ) 相比, 该策略在几乎
不损失精度的前提下, 将向量存储带宽降低至原始数据的 1/8. (2) 该方法设计了二级残差量化结构, 第 1 级量化结
果直接用于图索引的快速搜索, 第 2 级残差编码仅在高精度重排序时激活, 形成“粗筛-精排”的协同机制. (3) 在索
引构建层面, LVQ 实现了压缩向量直接构造近邻图, 其理论证明量化误差对图拓扑稳定性的影响呈正态分布, 通
过 4–8 比特量化即可保持剪枝规则的等效性, 使索引构建内存需求降低到 1/6 而不影响搜索质量.
在硬件加速层面: (1) 指令集优化, 设计了基于 AVX 指令集的向量解码与相似度计算的融合内核, 将压缩数据
流转化为 SIMD 友好的计算模式, 使单指令处理速度较 float16 提升 2.1 倍; (2) 访存能力增强, 针对图搜索的随机
访存特征, 提出基于预取偏移量与步长的自适应预取策略, 配合大页内存布局消除 TLB 失效, 实现 90% 的峰值内
存带宽利用率; (3) 并行架构适配, 通过扁平化数据结构和无锁队列设计, 在 40 核服务器上相交单线程达成 33 倍