# AST26: Product Quantization

> 這是 AST26 進階儲存系統的課程共筆，歡迎所有同學共同編輯與補充。
# 範例
完整走一遍，數字都簡化。

### 設定

- 資料庫有 12 筆 vector
- IVF 分成 3 個 cluster
- PQ 切成 2 段，每段有 4 個 centroid

---

### 建 index 階段

**Step 1：IVF 分群**

K-means 把 12 筆資料分成 3 個 cluster：

Cluster 0（運動類）：vector A, B, C, D
Cluster 1（食物類）：vector E, F, G, H
Cluster 2（科技類）：vector I, J, K, L

每個 cluster 有一個 centroid 代表它的中心位置。

**Step 2：PQ 壓縮每筆資料**

每筆 vector 壓縮成 compressed vector 存進自己的 cluster：

Cluster 0：A→[2,1], B→[3,0], C→[1,2], D→[0,3]
Cluster 1：E→[1,1], F→[2,3], G→[0,2], H→[3,1]
Cluster 2：I→[0,1], J→[1,3], K→[2,0], L→[3,2]

---

### 查詢階段

query 進來，假設是「籃球」相關的 vector。

**Step 1：IVF 找最近的 cluster**

query 跟 3 個 cluster centroid 算距離：

Cluster 0（運動類）centroid → 距離 0.2  ← 最近
Cluster 1（食物類）centroid → 距離 0.8
Cluster 2（科技類）centroid → 距離 0.9

nprobe = 1，所以只看 Cluster 0，跳過 Cluster 1 和 2。

**Step 2：ADC 建 lookup table**

query 切成 2 段，各跟 4 個 centroid 算距離：

        centroid 0  centroid 1  centroid 2  centroid 3
第1段      0.8         0.3         0.5         0.7
第2段      0.6         0.2         0.9         0.4

這裡的 centroid 0~3 是 PQ codebook 的 centroid，
不是 IVF 分群用的那 3 個 cluster centroid，兩者完全獨立。

**Step 3：查表算 Cluster 0 裡每筆的距離**

A [2,1] → 第1段查centroid 2→0.5，第2段查centroid 1→0.2，總距離=0.7
B [3,0] → 第1段查centroid 3→0.7，第2段查centroid 0→0.6，總距離=1.3
C [1,2] → 第1段查centroid 1→0.3，第2段查centroid 2→0.9，總距離=1.2
D [0,3] → 第1段查centroid 0→0.8，第2段查centroid 3→0.4，總距離=1.2

**Step 4：回傳結果**

距離最小的是 A（0.7），回傳 A。

---

### 總結分工

IVF：12筆 → 只看4筆（跳過8筆）
PQ+ADC：4筆 × 2次lookup = 8次查表就算完所有距離

(IVF) + (PQ + ADC)兩個合在一起，又少看資料，又快速計算。

# 再來用幾何的角度重新解釋。

每筆資料的 sub-vector，在子空間裡是一個**點**。

Codebook 的 256 個 centroid，是這個子空間裡的 **256 個代表點**。

壓縮 = 把這個點「捨入」到最近的代表點

就像地圖上你的位置是精確座標，但你說「我在台北車站附近」——用一個代表地點取代精確位置。

---

### ADC 的幾何意義

查詢時真正想算的是：

query 的第1段  ←→  資料A 的第1段    （精確距離）

但資料 A 的第1段已經被壓縮成 centroid 2 了，所以改成算：

query 的第1段  ←→  centroid 2       （近似距離）

幾何上就是這樣：

### 關鍵幾何概念

資料 A 已經被壓縮成 centroid 2 了，所以：

query 到 資料A 的距離
    ≈ query 到 centroid 2 的距離

這個近似成立，是因為資料 A 本來就在 centroid 2 附近（當初就是因為最近才被分到這群）。

而 query 到 centroid 2 的距離，**建 lookup table 的時候就算好了**，直接查就好。

---

### 所以 lookup table 的幾何意義

> 事先把 query 到每個 centroid 的距離都算好存起來，之後對每筆資料只需要查「它用的是哪個 centroid」，就能知道近似距離。

---