Product Quantization

當向量資料集大到無法全部放進 memory 時，我們需要壓縮向量的表示方式來實現 large-scale ANN search，這就是 product quantization（PQ）的核心動機。PQ 的做法是將高維向量切分成多個 sub-vector，對每個子空間獨立訓練 codebook，然後用 codebook 中最近的 centroid 編號來取代原始 sub-vector，大幅降低儲存需求。在查詢時，我們使用 asymmetric distance computation（ADC）——query 向量保持原始精度，只對 database 端的壓縮表示計算近似距離——以在壓縮率與搜尋精度之間取得良好平衡。我們也會介紹 IVF-PQ 如何結合 inverted file index 與 PQ，先用粗粒度的 clustering 縮小搜尋範圍，再用 PQ 進行 disk-resident 的 ANN 搜尋，使得十億級別的向量檢索成為可能。

Key Concepts

我理解 Product Quantization 的核心思想：將高維向量切分成多個 sub-vector，對每個子空間獨立訓練 codebook，用 centroid 編號取代原始 sub-vector 來達成壓縮

我理解 centroid encoding 如何大幅降低儲存需求：原本需要浮點數表示的 sub-vector 被壓縮成一個 codebook index，通常只需 8 bits

我理解 asymmetric distance computation（ADC）的運作方式：query 向量保持原始精度，只對 database 端的壓縮表示計算近似距離，在壓縮率與精度之間取得平衡

我理解 IVF-PQ 如何結合 inverted file index 的粗粒度 clustering 與 PQ 的向量壓縮，先縮小搜尋範圍再進行精細比對

我了解為什麼 PQ 與 IVF-PQ 的組合能使十億級別的向量檢索成為可能：透過壓縮讓向量可以 disk-resident，同時維持足夠的搜尋精度

Recommended Resources