Nearest Neighbor Search（最鄰近搜尋）概論
什麼是 Nearest Neighbor Search？
Nearest Neighbor Search（NNS, 最鄰近搜尋）是一種優化問題，其目的是在已知資料點集合 S 中，尋找與特定查詢點 q 距離最近（或最相似）的資料點。這種「距離」通常以不相似度函數（如歐幾里得距離、曼哈頓距離等）衡量，因此距離越小，兩點就越「近」。
形式化定義
- 給定點集 S 與查詢點 q，在 S 中找到與 q 距離最小者。
- 推廣問題：k-最近鄰搜尋（k-NN），找到前 k 個最近的點。
主要應用領域
- 模式識別與分類（如 KNN 分類法）
- 電腦視覺與圖像檢索
- 資料壓縮與編碼
- 拼字檢查、文字板模比對
- DNA 序列分析與資料庫搜尋
- 導航與定位系統
- 網路推薦與行銷
常見方法
精確搜尋（Exact Nearest Neighbor Search）
- 暴力搜尋（Brute-force）：對所有資料點逐一計算距離，準確但效率低，不適合大規模資料集。
- 樹狀結構：如 KD-Tree、Ball-Tree，適合中低維度資料，能顯著加速搜尋，維度過高則效能下降。
近似搜尋（Approximate Nearest Neighbor, ANN）
- 允許結果不是最接近但「夠接近」，以加快搜尋速度。
- 常用於高維空間或大規模資料場景，如向量相似度搜尋與推薦系統。
- 手法如：
- Locality-Sensitive Hashing (LSH)
- Proximity Graph（HNSW 等）
- 向量索引（如 FAISS, OpenSearch 的 ANN 模組）
演算法過程簡介
- 資料預處理：建立適當的索引資料結構（例如 KD-Tree，HNSW Graph）。
- 查詢：給定查詢點 q，快速篩選並計算候選點與 q 的距離。
- 排序與過濾：選出距離最小（或前 k 小）的點作為結果輸出。
特點與效能考量
- 精確搜尋：適合小型或低維資料，計算成本高。
- 近似搜尋：犧牲部分精確度，獲得大幅速度提升（適合千萬級以上資料或高維場景）。
- 距離量測：根據場景可選用不同度量（歐幾里得、餘弦相似度、曼哈頓等）。
現實應用案例
- 圖像/商品相似度檢索
- 語音辨識特徵比對
- 大規模推薦系統（如向量資料庫 ANN 搜尋）
- 空間定位與最近設施推薦
