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的誤差更小一些。

(圖片引自知乎:工牌廠程序猿)
浙公網安備 33010602011771號