Product Quantization

當向量資料集大到無法全部放進 memory 時，我們需要壓縮向量的表示方式來實現 large-scale ANN search。Product Quantization 的做法是將高維向量切分成多個 sub-vector，對每個子空間獨立訓練 codebook，然後用 codebook 中最近的 centroid 編號來取代原始 sub-vector。在查詢時，我們使用 asymmetric distance computation（ADC）：query 向量保持原始精度，只對 database 端的壓縮表示計算近似距離，以在壓縮率與搜尋精度之間取得良好平衡。我們也會介紹 IVF-PQ 如何結合 inverted file index 與 PQ，先用大範圍的 clustering 縮小搜尋範圍，再用 PQ 進行 ANN 搜尋。 （Product Quantization 在 RAG: Retrieval-Augmented Generation 也會介紹。）

貢獻 HackMD 共筆 💲大抄

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 的向量壓縮，先縮小搜尋範圍再進行精細比對

Recommended Resources