ANN = Approximate Nearest Neighbor（近似最近鄰搜尋）
在高維向量空間中，用較少計算成本找出「夠接近」查詢向量的 Top-K 候選
→ 不保證找到真正最近鄰，但換來大幅降低的搜尋延遲

常見應用：embedding 檢索、語意搜尋、推薦系統、RAG、向量資料庫

問題定義

給定：查詢向量 q，資料集 {v1, v2, ..., vn}
目標：找出與 q 最接近的 Top-K 向量

常見相似度計算：

為什麼不用 Exact KNN？

Exact KNN 直接掃描所有向量，理論最準，但：

資料量 1 億筆 × 每次 768 維向量
→ 每次查詢要做幾億次距離計算
→ 延遲太高，線上服務無法接受

→ 需要 ANN：先縮小候選集合，再精算

ANN 的核心取捨

recall ↑  ←→  latency ↓
memory ↑  ←→  speed ↑
build time ↑  ←→  query efficiency ↑

沒有免費的午餐：各種 ANN 方法都在這幾個維度間做平衡

方法一：Partition-based（IVF）

先把向量空間切成多個區域，查詢時只搜尋部分區域

建索引：K-Means 分群 → 每個向量掛到最近的 centroid bucket

查詢：
  q 進來
    ↓
  找最近的 nprobe 個 centroid
    ↓
  只掃描這些 bucket
    ↓
  回傳 Top-K

IVF（Inverted File Index）：FAISS 和 Milvus 的基礎組件

• nprobe 越大 → recall 越高，但速度越慢
• 分群品質（nlist）會影響 recall 上限

參考：FAISS Documentation — Meta AI

方法二：Quantization-based（PQ）

把原始高精度向量壓縮成短編碼，搜尋時比近似距離

原始向量（768 維 float32）
        ↓ 切成 M 段子空間
每段各自量化 → codebook index
        ↓
compact code 取代完整向量（記憶體省 8–32×）

PQ（Product Quantization）

• 壓縮率高，適合十億級向量庫
• 壓縮會帶來資訊損失，recall 通常略低

常見延伸：

• OPQ：先做旋轉，讓 PQ 更適合資料分佈
• IVF-PQ：先分區縮小候選，再量化比距離（最常見的實務組合）

參考：FAISS Documentation — Meta AI

方法三：Graph-based（HNSW）

把每個向量當節點，連邊到一些近鄰，查詢時沿邊走向更接近 q 的節點

上層（稀疏）：快速跳到大致區域
     ↓
下層（密集）：細部搜尋精確近鄰

HNSW, Hierarchical Navigable Small World

• recall 高、latency 穩定
• 建索引較慢，記憶體占用較高
• 目前最主流的高品質 ANN 方法

方法四：Hash-based（LSH）

用 locality-sensitive hashing 讓相近向量落在相同 bucket

對 q 做多組 hash → 只比對相同/相近 bucket 的候選

LSH（Locality-Sensitive Hashing）

• 理論清楚、早期主流
• 現代實務中通常被 IVF / HNSW / PQ 取代
• 適合特定相似度（如 Hamming distance）或研究用途

實務常見組合

如何評估 ANN

什麼時候選哪一種？

實際應用

語意搜尋：文件轉 embedding → 查詢時用 ANN 找最相近文件向量

推薦系統：使用者向量進來 → ANN 快速找出 Top-K 候選商品

RAG：問題 embedding → ANN 找候選 chunk → 送給 LLM 生成

pgvector 沒有 pre-filtering 時 ANN recall 會下降
參考：No pre-filtering in pgvector means reduced ANN recall — DEV Community

總結

ANN = 用近似答案換低延遲

四大類方法：
  Partition（IVF）  → 空間分區縮小搜尋範圍
  Quantization（PQ） → 壓縮向量省記憶體
  Graph（HNSW）     → 圖導航，高 recall
  Hash（LSH）       → 理論直觀，現代較少單獨使用

實務首選：IVF-PQ（大規模省記憶體）或 HNSW（高品質低延遲）

Related Notes

• HNSW, Hierarchical Navigable Small World
• Approximate Nearest Neighbor Search Instability

Sources

• FAISS Documentation — Meta AI
• Day20：向量壓縮與 ANN 搜尋 — iThome
• How do embeddings improve ANN search? — Milvus
• No pre-filtering in pgvector means reduced ANN recall — DEV Community