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

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

computation, SDC) 有所不同, 主要特点是不直接在查询向量上进行量化操作, 而是计算查询向量与已量化编码之
间的距离. 在需要更高准确率的近似最近邻搜索 (approximate nearest neighbor search) 场景中, 我们选择采用 ADC
算法, 确保在大规模数据集中的检索性能和准确度.

SDC: d(x,y) ≈ d(q(x),q(y)) (10)

ADC: d(x,y) ≈ d(q(x),y) (11)
RVQ 和 PQ 在距离计算中的主要区别体现在内积距离和 L2 距离的计算方法上. 对于 PQ 的量化结果, 通过分
别计算各个量化向量的距离, 并将其简单地组合起来, 就可以快速获得量化编码与查询向量之间的距离. 由于 PQ
采用了乘积量化的方式, 计算过程相对简便且高效.
在 RVQ 的情况下, 虽然可以通过单独计算各量化向量并求和的方法快速获得内积距离, 但计算 L2 距离时,
RVQ 表现出一定的不足. 这个问题的根源在于, RVQ 在处理多个量化器的情况下, 无法像 PQ 那样直接分解和计
算 L2 距离. 然而, 通过引入一个简单的距离计算公式就能有效地解决这一问题, 从而增强 RVQ 在距离计算方面
的能力, 使其能够在 L2 距离计算中表现得更加准确和高效. 这一公式在计算过程中结合了 RVQ 的残差信息, 从
而弥补了传统方法的不足.
在 RVQ 的背景下, 该过程涉及单独计算各个码字的距离, 然后将其相加以确定总距离. 尽管内积距离的计算
很快, 但 L2 距离需要额外的步骤. 尽管如此, 简单的距离计算公式的应用可以解决这个限制.

2
2
2
d(x,y) = ||x−y|| = ||x|| +||y|| −2x×y (12)
对于 RVQ, 公式 (12) 变换为:

n ∑
2
2
2
2
d(q(x),y) = ||q(x)|| +||y|| −2q(x)×y = ||q(x)|| +||y|| −2 c i ×y (13)
i=1
对于 WRVQ, 公式 (12) 变换为:

n ∑ i ∏
2
2
d(q(x),y) = ||q(x)|| +||y|| −2 c i ×y× d j (14)
i=1 j=0
在公式 (14) 中, 我们可以观察到第 1 项可以在索引构建过程中预先计算, 而第 2 项在搜索过程中每个查询向
量只需要计算一次. 这使得我们能够以与计算内积距离相同的时间复杂度计算 L2 距离.
在解决了搜索过程中距离计算的基本问题之后, 我们还发现, 相较于 PQ, RVQ 具有一个显著优势, 即其码字
并不完全相同. 即便在 OPQ 中, 由于码字对应的维度不同, 导致码字之间并不完全相等, 它们仍然保持着一定的平
行关系. 然而, RVQ 在这方面表现得更为独特. RVQ 的码字生成过程揭示了一个重要特性: 每个后续的码字本质
上是对前一个码字的“补充”, 它们在编码过程中形成了一个递增精度的序列. 随着码字数量的增加, 量化精度不断
提高. 这一特点使得 RVQ 在索引构建中具有独特优势, 特别是在处理大规模数据时, 能够更有效地提升查询精度.
3.2 量化索引构建
在索引构建过程中, 我们假设, 对于任何 k < n, 前 k 个码字可以作为簇中心, 而剩下的 n−k 个码字则表示相对
于该簇中心的残差. 这一假设是我们将向量量化步骤与搜索过程分开, 并将其视为独立的表示模型的关键原因.
基于这一特性, 我们开发了一种基于 WRVQ 的近似最近邻搜索 (ANN) 算法. 该索引将整个向量空间划分为 k
个区域, 每个向量由其区域中心向量和残差表示. 在 WRVQ 量化编码的表示中, 第 1 个码字表示簇中心, 而后续码
字则表示残差. 与传统的 IVFPQ 算法不同, 在 WRVQ 中, 表示残差和原始码字的码字本质上是相同的. 这一特点
使得可以使用倒排索引进一步划分残差, 同时, 划分后的残差表示也可以继续细分. 理想情况下, 当码本训练得足
够充分时, 我们可以基于 n 个码本构建一个 n 层的树结构索引.
然而, 这种理想状态在实际的码本训练中难以达到. 在实验中, 如果将所有的码本都用来构建树结构索引, 那
么搜索的性能和效率往往无法达到最佳. 除了码本的训练可能无法将所有向量正确地划分到应有的子空间外, 数
据集的规模也会导致在建立第 2 级或第 3 级节点时产生许多空节点. 这不仅会在索引构建过程中增加不必要的开
销, 还会使得在第 3 级之后的分类搜索失去意义. 例如, 在 10 个向量中搜索最近邻时, 根本没有必要在 8 个类别内