ANN 近似最近邻：为什么与四大路线

为什么不能暴力、召回率定义与代价、树/哈希/量化/图四大类方法对比，以及工业界现状。

为什么必须近似（ANN）

精确 k-NN 在数据量大、维度高时只能暴力扫描全部 N 个向量，耗时 ∝ N。当 N=1 亿、d=768，单次查询要算 768 亿次乘加，十几秒——无法服务在线请求。于是退一步：允许召回略有损失，换取几个数量级的加速，这就是近似最近邻（Approximate Nearest Neighbor, ANN）。

核心权衡：召回率（Recall）↔ 延迟（Latency）。ANN 用一点召回换巨大速度。

召回率（Recall）与它的代价

Recall@k = | 算法返回的 top-k ∩ 真实 top-k | / k

比如真实最近 10 个里，算法只找回 9 个，Recall@10 = 0.9。召回率越高，越接近暴力结果，但通常意味着要访问更多候选、更慢、更占内存。

语义检索场景，Recall@10 在 90%~99% 通常已够用（后面还有重排兜底）。
调参本质就是在"召回 vs 延迟 vs 内存"三角里挪动。

图 1：召回率—延迟权衡曲线（示意）。向右上走=更准但更慢。

四大类方法

① 基于树（Tree）

KD-tree / Ball-tree：按维度递归划分空间。低维（<20 维）高效，但高维时"维度灾难"下退化成近似暴力，实际用得少。

② 基于哈希（LSH）

局部敏感哈希：用随机超平面把相似向量以高概率分进同一桶，桶内再精排。有理论保证，但高维下内存大、召回不稳。详见《LSH 局部敏感哈希》。

③ 基于量化（Quantization）

乘积量化（PQ）把向量压缩成几十字节，检索时在压缩域算距离。内存极低，适合十亿级。IVF-PQ 是其代表。详见《IVF+PQ》。

④ 基于图（Graph）

HNSW / NSG：把向量建成"可导航小世界"图，查询沿边贪心逼近最近邻。当前工业界主流——高召回、低延迟。详见《HNSW》。

图 2：ANN 四大路线。当前生产环境以"图（HNSW）"和"量化（IVF-PQ）"为主。

横向对比

方法	高维适应性	召回	延迟	内存	动态写入
树(KD)	差	高	中	低	难
LSH	中	中	中	高	易
IVF-PQ	好	中高	低-中	极低	中
HNSW	好	高	低	高	中(删难)

工业界现状

在线、内存充足：HNSW 是默认答案（Faiss、Milvus、Qdrant、Weaviate 都支持）。
超大规模 / 内存受限：IVF-PQ、DiskANN（微软，磁盘上亿级）、ScaNN（Google）。
理论教学 / 特定场景：LSH、KD-tree 仍有价值，但生产主力是图与量化。

记住三件事：① 必须近似；② 召回换速度；③ 路线就四条，图与量化最实用。具体算法看本系列后续几篇。