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

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

同的阈值分配策略, 基于新的原理, 能够减少候选点的数量从而提高性能. 文献 [32] 设计了基于成本感知的空间
划分和阈值分配策略来优化搜索性能. 文献 [74] 进一步讨论了支持汉明距离的连接查询处理方法. 文献 [75] 提出
了允许重合的划分策略增强的鸽巢原理 (augmented pigeonhole principle, APP), 能够捕捉查询负载和数据集的关系
来优化查询, 并基于 APP 提出了一个高效的汉明空间索引框架以支持范围查询和 KNN 查询.
2.4 基于量化的数据组织方法
基于量化的方法主要目的是降低数据占用空间, 获得处理大规模数据的能力. 它将高精度的原始数据用低精
度的方式进行表示, 然后用整数进行编码, 在检索时根据存储的整数值查询码表将向量数据还原为低精度的表示.
下面介绍具体技术.
2.4.1 乘积量化
乘积量化 (product quantization) [15,33] 是将高维空间中的点用一个有限子集进行编码的过程. 其核心思想是将高
维向量分解为多个低维子空间, 并分别量化, 减少了码本的占用, 显著减少计算和存储开销. 乘积量化大概分为子
空间分解、独立量化、压缩表示和距离计算这 4 个方面. 图 5 展示了乘积量化的基本过程.

N条

(1) C 1 (2)
d/m维 ... C 1 3 3 2 ... 1
(4) (3)
C 1
C 1
(1) (2)
C 2 C 2
... (4) 2 1 4 ... 3
C 2 (3)
用质心的编号
C 2
划分为m个子空间 K-means聚类 (1) (2) 代表子向量
C 3 C 3
d维 ... ... (3) 1 2 3 ... 1
(4) C 3
C 3
... ... ...
(1) (2)
C m C m
... (4) (3) 4 2 1 ... 4
C m C m
图 5 乘积量化示意图

子空间分解: 将原始高维向量 (维度 d) 均匀切分为 m 个子空间, 每个子空间维度为 d/m. 例如, 128 维向量分成
8 个 16 维子空间. 独立量化: 对每个子空间单独进行 K-means 聚类, 生成 K 个质心 (如 K = 256). 每个子向量用最
近的质心编号 (1–K) 表示, 相当于用 8 位整数编码. 压缩表示: 原始向量被压缩为 m 个质心编号的组合 (如 8 个子
空间编号拼接), 存储空间从 d 个浮点数降至 m 个整数, 极大地节省了内存. 距离计算: 距离计算分为对称距离和非
对称距离. 对于前者, 查询向量和数据库中的向量都用质心来近似, 通过预计算的子空间质心距离表查表快速求
O(mK ); 对于后者, 仅数据库中的点用质心表示, 查询向量保
2
和, 需要为每个子空间维护一个表格, 空间复杂度为
留原始值, 因此在查询到来时需要先计算查询和质心的距离形成一个距离表, 额外维护 m 个表格的空间复杂度为
O(mK) , 后续搜索通过查表求和快速求解距离, 通常精度更好. 两种方法求与 N 个点的距离的复杂度都为 O(mN).
通过量化能够显著降低存储开销, 如 128 维向量内存占用可降至原来的 1/64, 适用于大规模向量检索的场景.
在基本的乘积量化的基础上, 有更多优化方法被提出来. 文献 [15] 讨论了许多基于乘积量化的工作, 包括但
不限于 Optimized PQ [76] 与 Cartesian K-means [77] 通过正交矩阵旋转空间以获取更好的码本; Additive quantization [78,79]
[81]
[80]
与 Composite quantization 用子空间质心的和拓展了乘积量化的表示方法; Optimized CK-means 、Tree quantization [82]
与 Sparse PQ [83] 使用不同的编码策略以得到更准确的查询结果. 此外, DPQ [84] 额外量化了数据到其最近聚类质心的
残差距离, DCPQ [85] 通过基于学习的方法维护码本, RVPQ [86] 为每个子空间构建由多个有序残差码本组成的残差层
次结构, CHPQ [87] 根据数据特征局部优化码本, 文献 [88] 提出 Fast-Scan 策略来充分利用 SIMD (single instruction