风车车知识库

ann-overview-beginner-report

26分钟阅读

ANN（Approximate Nearest Neighbor）综述：从问题定义到主流算法路线

一句话总结

ANN（近似最近邻搜索）要解决的是：面对海量高维向量，如何不做全量扫描，也能很快找到“最像”的那几个点。 过去二十多年，业界和学界逐渐形成了几条主流路线：哈希、树、量化、图、磁盘图索引，以及它们的混合系统。 如果只记一句话，那么就是：

ANN 的本质，是在“速度、精度、内存、构建成本、更新能力”之间做结构化取舍。

这份报告写给谁

这篇报告按“数学小白也能读懂”的方式来讲，重点不是公式推导，而是：

  • ANN 到底是什么问题
  • 为什么这个问题这么难
  • 主流方法到底各自像什么
  • 重要论文各自贡献了什么
  • 为什么今天很多系统最终偏爱 HNSW / IVF-PQ / DiskANN 这几条路

先讲最基本的问题：什么叫最近邻搜索

假设我们有很多向量：

  • 文本 embedding
  • 图片 embedding
  • 用户画像向量
  • 商品向量
  • 多模态表示向量

当你给我一个查询向量 q 时，我想找数据库中距离它最近的若干个点。

这就叫：

  • Nearest Neighbor Search（最近邻搜索）
  • 或者更常见地找 Top-K：K-Nearest Neighbor Search

最笨的方法

最直接的办法就是：

  • 拿 q 和库里每个点都算一遍距离
  • 然后选最小的 K 个

这叫 brute-force / linear scan。

它的优点：

  • 绝对正确
  • 实现最简单

它的缺点：

  • 数据量一大就太慢
  • 尤其当数据规模从百万到十亿时，几乎不可接受

所以 ANN 研究关注的问题是：

能不能不看所有点，也还能找到几乎正确的答案？

ANN 和精确搜索的区别

精确最近邻

要求：

  • 找到的就是“真正最近”的点
  • 一个都不能错

近似最近邻 ANN

允许：

  • 偶尔不完全最优
  • 只要大多数情况下足够接近真值即可

换来的好处：

  • 大幅提速
  • 降低内存访问
  • 可以支撑大规模向量检索系统

所以 ANN 不是“做错了”，而是：

主动接受一点点误差，换取巨大的系统效率收益。

为什么高维会让问题变难

这是 ANN 里最核心的背景问题之一。

低维时，树通常很好用

比如二维平面里找最近点：

  • 你可以很容易把空间切块
  • 很多点可以快速排除

高维时，空间切分开始失效

当维度很高，比如 128 维、384 维、768 维时：

  • 数据越来越稀
  • 很多“边界剪枝”不再明显
  • 树结构很容易退化

这就是大家常说的：

  • curse of dimensionality（维度灾难）

它不是说“高维完全不能搜”，而是说：

低维里那些很好用的几何直觉，在高维下会迅速失灵。

这也是 ANN 百家争鸣的根本原因。

ANN 系统到底在权衡什么

ANN 不是一个单指标优化问题，而是多目标平衡。

通常要同时考虑：

1. 查询延迟

一次 query 多快返回。

2. Recall

是不是把真正的近邻找回来了。

3. 吞吐

单位时间能处理多少查询。

4. 内存占用

索引会不会太大。

5. 构建成本

建索引快不快。

6. 更新能力

新数据能不能增量插入，旧数据能不能删除。

7. 存储介质

全在内存里，还是要依赖 SSD / NVMe。

一个方法快，不代表它整体最好；它可能：

  • 占内存太大
  • 更新太差
  • 构建太慢
  • 或者 recall 不够

所以 ANN 本质上是系统工程问题。

评价 ANN 最常见的指标

Recall

最重要。

如果真实 Top-10 里你找回了 9 个：

  • recall = 0.9

Recall 越高越接近真值。

QPS / Latency

  • QPS：每秒查询数
  • Latency：单次查询耗时

Build time

索引构建时间。

Memory footprint

索引内存大小。

Index size on disk

磁盘索引大小，尤其对磁盘型 ANN 很重要。

所以论文常见比较方式是：

在固定 recall 下，谁更快；或者在固定延迟下，谁 recall 更高。

ANN 的主要技术路线图

把几十年工作压缩一下，可以粗分成几类：

  1. 树方法：KD-tree、随机投影树、Annoy 一类
  2. 哈希方法：LSH 一类
  3. 量化方法：PQ、IVF-PQ、ADC、OPQ、ScaNN 一类
  4. 图方法：NSW、HNSW、NSG 一类
  5. 磁盘图方法：DiskANN 一类
  6. 混合系统：粗筛 + 精排 / 内存 + 磁盘 / 分区 + 图 / 分区 + PQ

下面按路线讲。

第一部分：哈希路线 —— LSH

直觉是什么

LSH（Locality-Sensitive Hashing）想做的事很朴素：

设计一种哈希，让“近的点更容易落到同一个桶里，远的点不容易”。

这和普通哈希恰好相反：

  • 普通哈希希望分得尽量散
  • LSH 希望保留“近似邻近关系”

数学小白版理解

想象你把空间切成很多随机投影形成的签名：

  • 两个点很近，它们的签名大概率相似
  • 两个点很远，它们的签名大概率不同

检索时：

  • 不用扫全库
  • 只去看和 query 哈希值相同/相近的那些桶

代表论文

Gionis, Indyk, Motwani (1999)

Similarity Search in High Dimensions via Hashing

论文摘要里最核心的意思是：

  • 高维下树方法会被维度灾难打爆
  • 近似搜索在很多实际应用里已经够用
  • 可以通过哈希让近邻更高概率碰撞，从而加速搜索

优点

  • 理论味很强
  • 对某些距离族有漂亮分析
  • 适合做概率保证型 ANN

缺点

  • 桶设计和参数调优比较麻烦
  • 很多场景下工程效果不如后来图方法强
  • 在现代 embedding 检索里，不再是最主流的默认首选

你可以怎么记住它

LSH = 用“保邻近”的哈希来缩小候选集合。

第二部分：树路线 —— KD-tree、随机投影树、Annoy

直觉是什么

树方法想做的是：

把空间一层层切开，让 query 只访问少量区域，而不是全空间。

低维时这非常自然。

为什么后来不再统治高维 ANN

因为维度高了之后：

  • 每次切分排除不了太多点
  • 树深了也不代表有效剪枝
  • 最终访问的节点可能还是很多

代表思路

KD-tree / randomized tree / FLANN

早期很经典。

  • 低维或中低维仍然有价值
  • 在某些数据上仍然实用

Annoy

Spotify 开源的经典库。 它本质上是：

  • 多棵随机投影树
  • 查询时同时走多棵树
  • 聚合候选

Annoy 的优点：

  • 实现简单
  • 好部署
  • 静态只读服务很方便

缺点：

  • 在很多高 recall、高维、大规模场景下，往往不如 HNSW 强

你可以怎么记住它

树方法 = 先把空间切块，再只搜一小部分块。

它是最符合直觉的一路，但在高维里不是最强的一路。

第三部分：量化路线 —— PQ、IVF-PQ、Faiss、ScaNN

这条路线在工业界极其重要。

核心直觉

量化路线想做的是：

把向量压缩成短码，用短码快速估计距离，而不是总拿原始向量硬算。

换句话说：

  • 少存点
  • 少算点
  • 更容易扩展到超大库

代表论文 1：Jégou et al. (2011)

这篇论文是 PQ 路线的里程碑。

它的核心想法

把一个高维向量切成多个子空间：

  • 每个子空间分别量化
  • 每段只存一个短小的 code
  • 整个向量就变成多个 code 拼起来的短码

然后距离不再直接用原始向量算，而是：

  • 通过查表快速估计

为什么这很强

因为：

  • 存储从“原始浮点向量”变成“紧凑编码”
  • 距离计算也从大量浮点乘加，变成更轻量的查表

这篇论文摘要的核心内容

它明确说：

  • 把空间拆成多个低维子空间
  • 每个子空间单独量化
  • 通过编码快速估计欧氏距离
  • 再加 inverted file system 时效果更强
  • 在十亿甚至二十亿级数据上具有很好扩展性

IVF 是什么

IVF = Inverted File

你可以理解成：

  • 先做一个粗聚类
  • 数据先分桶
  • query 先找最可能的几个桶
  • 再只在这些桶里做更细的 ANN

所以 IVF 的角色是：

粗筛候选分区

而 PQ 的角色是：

压缩和快速距离估计

这两个经常组合起来，就是：

  • IVF-PQ

为什么 IVF-PQ 这么常见

因为它同时解决了两个大问题：

  1. 不用搜全库，只搜部分桶
  2. 候选点也不是原始全精度向量，而是压缩码

所以它特别适合：

  • 超大规模库
  • GPU/CPU 批量检索
  • 内存压力敏感场景

代表论文 2：Johnson et al. (2017)

Billion-scale similarity search with GPUs

这篇论文也是 Faiss 路线的代表作。

它干了什么

核心不是提出全新 ANN 基础理论，而是：

  • 把相似搜索在 GPU 上做得极强
  • 优化 top-k selection、内存层次、PQ 搜索等关键路径
  • 让十亿级相似搜索真正变得可工程化

这篇论文的重要意义

它告诉大家：

ANN 不只是索引结构问题，还是硬件利用问题。

后来的很多系统实践都深受影响。

代表论文 3：Guo et al. (2020)

Accelerating Large-Scale Inference with Anisotropic Vector Quantization

这是 ScaNN 背后的代表论文。

它的核心想法

传统量化方法主要最小化“重建误差”。 但在最大内积搜索（MIPS）里，真正重要的不是所有方向都同样精确，而是：

对影响排序最关键的方向，误差要更小。

ScaNN 的工作重点就是：

  • 不再只追求一般性的重建精度
  • 而是让量化更贴合检索目标本身

为什么重要

这说明量化路线在进化：

  • 早期 PQ 更像通用压缩
  • 后来的方法更像“任务感知型压缩”

量化路线的优点

  • 内存效率高
  • 更适合超大规模数据
  • 很适合 GPU 和批量检索
  • 工业界成熟度非常高

量化路线的缺点

  • 通常需要训练码本 / 聚类中心
  • 系统比单纯图结构更复杂
  • 极高 recall 下未必总能赢图方法
  • 更新/增量维护不一定像图那么自然

你可以怎么记住它

量化路线 = 先粗筛，再用压缩码快速比距离。

第四部分：图路线 —— NSW / HNSW

核心直觉

图路线想做的是：

把数据点连成一张“可导航”的图，然后让 query 在图上走，越走越接近目标。

这条路线在今天极其重要。

基础版：NSW

单层小世界图。

  • 点连到邻居
  • 查询从入口开始贪心走
  • 借助 small world 性质快速接近目标

但 NSW 有缺点：

  • 单层图既要负责远程导航又要负责局部精修
  • 在低维、聚簇数据上可能退化

里程碑：Malkov & Yashunin (2016/2018)

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

这就是 HNSW。

为什么它这么重要

它把图索引推进到了一个非常好用的工程平衡点：

  • 多层结构
  • 高层做长距离导航
  • 低层做局部精修
  • 用更聪明的邻居选择 heuristic 保持图可导航性

为什么今天 HNSW 这么火

因为它同时满足：

  • 快
  • recall 高
  • 增量构建友好
  • 工程上不算复杂
  • 对多种数据分布比较稳健

如果要一句话概括：

HNSW = 图版 skip list。

风车车前面已经给爹单独写过这篇精读。

图路线的优点

  • 高 recall 表现强
  • 很多 embedding 场景下效果非常好
  • 参数相对直观（如 M, efSearch, efConstruction）
  • 查询延迟表现常常很优秀

图路线的缺点

  • 内存占用往往不低
  • 大规模删除/压缩/重构更麻烦
  • 超大规模下，纯内存图会遇到容量问题

你可以怎么记住它

图路线 = 让 query 在一张好导航的图里“走路找近邻”。

第五部分：磁盘图路线 —— DiskANN

当数据继续大到：

  • 内存放不下
  • 但又想要高 recall、高吞吐

就需要新的路线。

核心问题

图索引很强，但纯图索引的一个大问题是：

  • 图通常更偏内存型
  • 数据到十亿量级时，内存压力巨大

那么问题来了：

能不能保留图索引的导航能力，同时把大部分数据放到 SSD 上？

代表工作：DiskANN

DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node

GitHub 项目自己的描述很直接：

  • Graph-structured Indices for Scalable, Fast, Fresh and Filtered Approximate Nearest Neighbor Search

它的核心思想

可以粗略理解为：

  • 仍然保留图导航思想
  • 但把图和数据布局设计成更适合磁盘访问
  • 尽量让 SSD 访问模式更高效
  • 让超大规模 ANN 在单机上也能做到高精度、高吞吐

为什么它重要

因为它补上了图路线的一大短板：

  • 纯内存太贵

DiskANN 所代表的，是 ANN 从“内存索引算法”走向“存储层级协同系统”的方向。

你可以怎么记住它

DiskANN = 把图索引从内存世界推进到 SSD 世界。

第六部分：ANN 不只是算法，还是系统设计

很多人初学 ANN，会以为：

  • 选一个算法就完了

其实不是。

真正系统通常是多层结构：

  1. 粗筛：分区 / 聚类 / 哈希 / 路由
  2. 候选生成：图 / PQ / 量化 / 树
  3. 精排：原始向量重算距离
  4. 缓存 / 内存 / SSD 分层
  5. 增量更新 / 合并 / compaction

所以 ANN 更像数据库或检索系统设计问题，而不仅是单个算法问题。

现代常见组合

1. IVF + PQ

  • 适合超大库
  • 内存效率高
  • GPU 很友好

2. HNSW

  • 适合高 recall、低延迟、内存足够的场景
  • 也是很多向量数据库的默认索引

3. DiskANN

  • 适合超大规模、单机 SSD 场景

4. Graph + quantization / rerank

  • 越来越多系统采用混合方案

第七部分：benchmark 视角告诉我们什么

代表工作

Aumüller et al. (2018)

ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms

它的重要意义

这篇工作最大的贡献不是提出新索引，而是：

让大家能在统一框架下比较不同 ANN 方法。

这很重要，因为 ANN 太工程化了：

  • 参数很多
  • 数据集差异很大
  • 一个方法在 A 数据集强，不代表在 B 数据集也强

ANN-Benchmarks 的一个非常重要的启发是：

没有绝对最好的 ANN 方法，只有更适合某个工作负载的方法。

这点非常值得记住。

第八部分：怎么建立一个“ANN 方法全景图”

如果把前面内容压成一张脑图，可以这么记：

路线 A：哈希

  • 代表：LSH
  • 核心：近点更容易碰撞进同一桶
  • 关键词：概率保证、桶检索

路线 B：树

  • 代表：KD-tree、随机投影树、Annoy
  • 核心：递归切空间
  • 关键词：空间分割、低维友好

路线 C：量化

  • 代表：PQ、IVF-PQ、Faiss、ScaNN
  • 核心：粗分区 + 压缩编码 + 快速距离估计
  • 关键词：省内存、超大规模、高吞吐

路线 D：图

  • 代表：NSW、HNSW
  • 核心：可导航图
  • 关键词：高 recall、低延迟、工程强势

路线 E：磁盘图

  • 代表：DiskANN
  • 核心：图索引 + SSD 友好布局
  • 关键词：十亿规模、单机、存储层级协同

第九部分：如果我是初学者，我该怎么判断该学哪条路线

如果你想先建立全局认知

建议顺序：

  1. 先理解 ANN 问题定义和 recall
  2. 看 LSH：理解“近邻保真哈希”这个经典思路
  3. 看 PQ：理解“压缩 + 距离近似”
  4. 看 HNSW：理解“图导航”
  5. 看 DiskANN：理解“系统化扩展到磁盘”

如果你想更贴近今天工业界

建议顺序：

  1. 先看 HNSW
  2. 再看 IVF-PQ / Faiss
  3. 再看 DiskANN
  4. 最后补 LSH 和树，作为历史与理论背景

原因很简单：

  • 现在很多生产系统最常见的核心路径就是图和量化

第十部分：如果我是工程师，我最该关心什么

1. 你的目标是高 recall 还是便宜吞吐

  • 高 recall、低延迟、内存够：优先考虑图（如 HNSW）
  • 超大规模、成本敏感：优先考虑量化（如 IVF-PQ）
  • 数据上 SSD：看 DiskANN

2. 数据是静态还是动态

  • 动态插入多：图方法通常更自然
  • 批量离线构建：量化路线也很强

3. 内存预算多大

  • 图通常更吃内存
  • PQ/压缩路线更省

4. 距离类型是什么

  • L2 / cosine / inner product 会影响适合的方法
  • MIPS 问题下很多系统会做额外变换或专门优化

5. 你要不要 rerank

很多系统不是一次性给最终答案，而是：

  • 先 ANN 找 100~1000 个候选
  • 再用原始向量精排

这通常能显著改善最终质量。

第十一部分：我对 ANN 这件事的整体理解

我觉得 ANN 领域最值得记住的不是单个算法，而是这三个大方向：

方向 1：不要硬刚精确性

ANN 的伟大之处在于：

  • 它接受“几乎正确”
  • 从而把系统做大、做快、做实用

方向 2：结构比暴力更重要

真正快的系统，不是更快地算所有点， 而是：

  • 让大部分点根本不用算
  • 或者只用粗算

方向 3：今天最强的方法，本质都在做“候选缩减”

不同方法看起来很不一样，但本质都在做同一件事：

先缩小候选集，再更认真地算候选。

  • 哈希：用桶缩小候选
  • 树：用空间切分缩小候选
  • IVF：用聚类桶缩小候选
  • 图：用导航路径缩小候选
  • DiskANN：用图 + 存储布局缩小候选

所以 ANN 的统一视角就是：

不要搜索整个空间，而要快速找到“最值得认真算的那一小撮点”。

第十二部分：给初学者的最终复述

如果爹只想记住最核心的一版，可以记下面这段：

ANN 是解决“如何在海量高维向量里快速找到最相似项”的技术。它之所以难，是因为高维让传统树索引很容易失效。后来形成了几条主要路线：LSH 用哈希缩小候选；树方法用空间切分缩小候选；PQ/IVF-PQ 用分区和压缩码降低搜索成本；HNSW 用多层图做高效导航；DiskANN 则把图索引推进到 SSD 场景。今天工业界最常见、最有代表性的主线，大致就是图索引和量化索引，以及二者与系统工程的混合体。

重要资料与论文清单

问题背景与基准

哈希路线

量化路线

图路线

  • Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (Malkov & Yashunin, 2016/2018)
    https://arxiv.org/abs/1603.09320

磁盘图路线

可以继续展开的后续主题

  • IVF / PQ / OPQ / ADC 到底各自是什么关系？
  • MIPS（最大内积搜索）和普通 ANN 有什么区别？
  • 向量数据库为什么常常提供 HNSW 和 IVF-PQ 两套索引？
  • DiskANN 和 HNSW 的系统边界分别在哪里？
  • 如何根据 recall、延迟、内存预算来选 ANN 索引？

关系图谱

反向链接