ANN（Approximate Nearest Neighbor 近似最近邻搜索）
在 百万-十亿级高维向量 中，毫秒级找到与查询向量"最相似"的 Top-K 候选 — 准确度换速度的工程取舍，是 向量数据库 性能的物理上限。
定义
最近邻搜索（k-NN） 在高维空间是 NP-hard 难题：暴力线性扫描 N 个 d 维向量需 O(N·d)，百万向量+1k 维 = 单查询数十毫秒-数秒，无法满足在线检索 SLA。
ANN 用近似度换速度：不保证返回的 Top-K 是"全局精确最优"，只保证 召回率（recall） 在可控范围（典型 90-99%），但延迟降低 100-1000 倍。没有 ANN 就没有现代 向量数据库。
核心算法家族
| 算法 | 原理 | 典型代表 |
|---|---|---|
| HNSW | 多层图，类似跳表 | hnswlib / Milvus / Weaviate 默认 |
| IVF（倒排文件） | k-means 聚类粗筛 | Faiss / Milvus |
| PQ / OPQ（乘积量化） | 向量压缩 4-32× | Faiss / Milvus 大规模场景 |
| DiskANN | 磁盘原生大规模 | Microsoft 出品 |
| ScaNN | Google 内部，剪枝+量化 | Google Cloud 内置 |
| SPANN | 内存+磁盘混合 | Microsoft 学术 |
| LSH（局部敏感哈希） | 哈希分桶 | 早期方案，已少用 |
关键工程指标
| 指标 | 含义 |
|---|---|
| 召回率（Recall@K） | 返回 Top-K 与真实 Top-K 的重叠率 |
| QPS | 每秒查询数 |
| P99 延迟 | 99% 查询的延迟上限 |
| 内存占用 | 单位向量索引开销 |
| 构建时间 | 全量索引构建耗时 |
性能边界
- HNSW：召回 95-99%、QPS 高、内存大（向量 3-5×）
- IVF-PQ：召回 80-95%、QPS 高、内存小（节省 8-32×）
- DiskANN：召回 95%、磁盘原生、十亿向量可达
主要工业实现
- Faiss（Meta）— 学术界事实标准
- hnswlib（Yury Malkov）— HNSW 经典实现
- Milvus / Pinecone / Weaviate / Qdrant — 商业向量数据库内置
- pgvector — PostgreSQL 插件（用 HNSW / IVFFlat）
关键演进
- 1998 k-d tree（早期低维有效，高维灾难）
- 2008 LSH 大规模化
- 2016 Faiss 开源 → 工业级 ANN 普及
- 2018 HNSW 论文（Y. Malkov）→ 成为主流
- 2024-25 DiskANN / SPANN 走向十亿级 + 量化压缩极致优化
相关
∈ belongs_to::3-07-AI原生中间件与开发平台