PQ算法全稱ProductQuantization，中文名為乘積量化。該算法來源于圖像檢索，本質上是對向量做壓縮。

假如總共有N個數據點，數據的維度是D維。給定一個Query做近鄰檢索，如果采用暴力檢索方式，那么計算復雜度就是N*D(遍歷N個點計算距離，每個點計算的復雜度是D)。如果可以對向量進行壓縮，比如壓縮后的向量維度只有原來的一半，那么復雜度就可以降低一半。

如下圖所示，假如原始的向量長度為128(D=128)，將向量分為8段(M=8)，每段的長度是16維。

采用聚類算法，對于每段訓練一個256個(k=256)中心的聚類模型，用聚類中心id表示每一段。由于聚類id有256個，所以只需要8-bits就可以表示一個id。注意每一段都是獨立的聚類模型和聚類中心點。

SDC全稱symmetric distancecomputation，是將query向量做壓縮，轉化為用每段用聚類中心id的向量表示。然后計算距離(此時所有待檢索的數據點都已經預先轉化完成向量壓縮)。而ADC算法，則是不對Query向量做壓縮，直接計算Query向量到各個聚類中心的距離。一般認為ADC的誤差更小一些。

（圖片引自知乎：工牌廠程序猿）