ANN（近似最近鄰）算法主要分為三類技術路線：基于樹的方法、哈希方法和圖方法，它們在原理、性能及適用場景上有顯著差異：

---

1. 基于樹的方法

核心原理：遞歸劃分數據空間形成樹狀結構（如二叉樹或多叉樹），通過樹遍歷快速篩選候選點。
典型算法：

• KD-Tree：按維度交替分割空間，適合低維數據（維度 < 20）。高維時性能退化明顯（“維度災難”）。
• Annoy（Approximate Nearest Neighbors Oh Yeah）：構建多棵二叉樹，通過投票機制提升召回率。平衡精度與速度，支持分布式索引（如Spotify推薦系統）。

適用場景：
? 低維空間精確搜索（如2D/3D地理位置檢索）
? 中等規模數據集（百萬級）
?? 高維數據效率低，需配合降維技術

---

2. 哈希方法

核心原理：將高維數據映射為低維二進制編碼（哈希桶），相似點落在相同或相鄰桶中。
典型算法：

• 局部敏感哈希（LSH）：設計哈希函數使相似點碰撞概率高。內存占用低，但參數調優復雜，召回率不穩定。
• 乘積量化（PQ）：將向量分割為子向量并分別量化，組合碼本壓縮表示。壓縮比高，適合超大向量庫（如十億級圖像檢索）。

適用場景：
? 超大規模高維數據（如圖像/視頻特征檢索）
? 資源受限環境（低內存、分布式存儲）
?? 二進制編碼損失信息，精度略低于圖方法

---

3. 圖方法

核心原理：構建近鄰圖（節點=數據點，邊=相似關系），通過圖遍歷查找最近鄰。
典型算法：

• HNSW（Hierarchical Navigable Small World）：多層圖結構，高層為“高速路”快速定位，底層精細搜索。查詢速度最快，精度接近暴力搜索。
• NSG（Navigating Spreading-out Graph）：優化圖連通性，減少冗余邊。內存效率更高，適合對內存敏感場景。

適用場景：
? 高精度實時檢索（推薦系統、語義匹配）
? 十億級高維數據（如OpenAI Embedding檢索）
?? 建圖時間長，動態更新成本高

---

對比總結與選型建議

方法	精度	查詢速度	內存占用	適用場景
樹方法	中高	中	低	低維數據、中等規模數據集
哈希方法	中	快	極低	超大規模數據、資源受限環境
圖方法	極高	極快	高	高精度實時檢索、十億級向量庫

決策參考：

• 需求高精度+低延遲 → 選擇 HNSW；
• 數據規模超大規模+內存敏感 → 選擇 PQ哈希；
• 維度低于20維 → 選擇 KD-Tree。