# 分治 Quantization
PQ 算法把 D 维向量分成 m 组， 每组进行 Kmeans 聚类算法
带来的好处
- m 组子向量的 Kmeans 算法可以并行求解
- 表示空间增大， K 的 m 次方
# 图示 PQ 算法生成码本与量化的过程
SDC 的计算流示意图
ADC 的计算流程 示意图
SDC 与 ADC 的整体复杂度为 O (N*m)， 此时的近邻计算是对整体的 N 来计算，实际中的 N 在现实应用中可能在千万量级以上， 虽然相较于暴力计算已经减少了计算量， 但计算量依然很大 并不实用。
IVFPQ
找 query 的 topk 最近邻， 不用对整个数据集 N 做计算， 只需要对 “有潜力” 的候选进行计算， 可以通过聚类的方式， 先找到 top 的 cluster， 然后对 cluster 内的数据点一次计算距离
- coarse quantizer，粗粒度量化器，在原始的向量空间中，基于 kmeans 聚类出 k' 个簇 cluster, k' 的大小一般为 sqrt (n),
- 实用 PQ 对 cluster 内的数据点进行量化，PQ 并不是直接在原始数据上做，而是经过第 1 层量化后，计算出每个数据与其量化中心的残差后，对这个残差数据集进行 PQ 量化。用 PQ 处理残差，而不是原始数据的原因是残差的方差或者能量比原始数据的方差或者能量要小
query 查询 topk 近邻时， 选定的粗聚类中心不一定是 1 个， 可以是多个， 比如 k'', 朴素的 ADC 算法的复杂度是 O (n×m)，而 IVFADC 算法的复杂度会降低为 O ((N×k''/k')×m)。
