近似最近邻（ANN）算法详细解析

最近邻搜索 （Nearest Neighbor Search）是指在给定一个查询向量时，从海量数据集中找到与之距离最近（最相似）的向量。精确最近邻需要遍历整个数据集，计算所有向量与查询向量的距离，这在数据量小、维度低时可行，但一旦数据达到百万、亿级且维度高达几百甚至上千，暴力搜索就变得不可行。

1

什么是近似最近邻（ANN）？

近似最近邻（Approximate Nearest Neighbor, ANN） 的核心思想是： 在可接受的精度损失下，大幅提升搜索速度 。也就是说，它找到的可能不是绝对最近的邻居，但通常是“足够近”的，并且搜索时间可以快几个数量级。

类比：

• 精确搜索 ：你在图书馆找一本特定的书，必须一本一本核对书名，直到找到正确的那本。
• 近似搜索 ：你根据图书分类、热门程度、作者等线索，直接去可能包含目标书的几个书架查找，虽然有可能错过，但绝大多数时候你能很快找到很接近的书。

2

ANN算法的基本原理

所有ANN算法都遵循一个通用框架： 构建索引 + 搜索索引 。

1. 构建索引（离线阶段）

对原始数据集进行预处理，建立一种特殊的索引结构。

这个结构可以是树、图、哈希表或量化码本，目的是将相似的向量“聚类”或“链接”在一起，以便在搜索时快速缩小范围。

2. 搜索索引（在线阶段）

给定查询向量，利用索引结构快速定位到候选区域。

在这些候选区域中进行距离计算，返回最相似的K个结果。

3. 核心权衡

ANN算法必须在三个指标间平衡：

• 召回率 ：找到的真实最近邻的比例（精度）
• 查询速度 ：每次搜索所需的时间
• 内存占用 ：索引所需的内存空间

3

主流的ANN算法及其原理步骤

1. HNSW（Hierarchical Navigable Small World）—— 基于图的方法

原理 ：构建多层图结构，上层图稀疏（长距离跳跃），下层图密集（精细搜索）。搜索时从顶层开始，快速定位到查询点所在区域，然后逐层向下细化。

步骤 ：

建图 ：

• 将每个向量看作图中的一个节点。
• 为每个节点建立与若干最相似节点的连接（“朋友列表”）。
• 构建多层结构：顶层节点最少，连接最远；底层节点最多，连接最近。

搜索 ：

• 从顶层的一个随机入口节点开始。
• 在当前层贪婪地移动到距离查询更近的邻居，直到无法更近。
• 将当前节点作为下一层的入口，重复步骤2，直到最底层。
• 在最底层收集K个最近邻居。

特点 ：速度极快，召回率高，但内存占用较大（需存储图结构）。

2. IVF（Inverted File Index）—— 基于聚类的方法

原理 ：先对数据集进行聚类（如K-means），将向量分配到不同的簇（Voronoi单元）。搜索时只查询与查询点最近的几个簇内的向量。

步骤 ：

建索引 ：

• 用K-means将数据集聚成nlist个簇，得到每个簇的中心向量。
• 将每个向量分配到离它最近的簇，并记录在倒排列表中（每个簇一个列表）。

搜索 ：

• 计算查询向量与所有簇中心的距离，选出最近的nprobe个簇。
• 只在这nprobe个簇的倒排列表中，暴力计算所有向量与查询的距离。
• 返回全局最近的K个结果。

特点 ：内存效率高，适合超大規模数据，召回率由nprobe控制（nprobe越大越精确，但越慢）。

3. PQ（Product Quantization）—— 基于量化的方法

原理 ：将高维向量分解成多个子向量，分别量化，用码本表示，极大压缩向量存储空间，同时支持快速距离计算（通过查表）。

步骤 ：

建索引 ：

• 将每个d维向量切分成m段子向量。
• 对每段子向量分别进行聚类（如K-means），得到m个码本，每个码本包含k个聚类中心。
• 用每个子向量最近的聚类中心ID（即量化值）来代表原始向量，实现压缩。

搜索 ：

• 对查询向量进行相同的切分。
• 预先计算查询向量的各段子向量与对应码本中每个聚类中心的距离，形成m×k的距离表。
• 对于数据集中的每个向量（由m个量化ID组成），通过查表快速累加各段距离，得到近似距离。
• 根据近似距离排序，返回最近的K个结果。

特点 ：压缩比极高（内存占用可降低几十倍），适合内存受限的场景，但可能损失一定精度。

4. LSH（Locality-Sensitive Hashing）—— 基于哈希的方法

原理 ：设计一组哈希函数，使得相似的向量有更高概率被哈希到同一个桶中。搜索时只需查询查询点所在桶内的向量。

步骤 ：

建索引 ：

• 选择一组局部敏感哈希函数（如随机超平面投影）。
• 对每个向量，用这组函数计算哈希值，组成哈希签名。
• 将相同签名的向量放入同一个桶。

搜索 ：

• 计算查询向量的哈希签名。
• 取出对应桶中的所有向量，进行精确距离计算。
• 返回最近的K个结果。

特点 ：理论保证强，但实际应用中为了达到高召回率需要很多哈希表，内存和查询时间可能较大。

4

ANN算法对比

5

ANN算法的适用场景

1. 大规模向量检索

• 图像检索 ：以图搜图，从百万级图像库中快速找到相似图像。
• 文本语义搜索 ：在文档库中搜索与查询语义相近的段落（RAG的核心）。
• 视频指纹 ：快速识别相似视频片段。

2. 实时推荐系统

• 用户行为向量化后，从商品向量库中快速召回候选商品。
• 新闻App根据用户兴趣向量秒级推荐相似文章。

3. 重复检测与去重

检测相似图片、新闻、代码片段等，防止重复入库。

4. 异常检测

正常模式向量构建索引，新向量如果离最近邻较远，视为异常。

5. 机器人领域

• 场景识别 ：机器人实时摄像头画面向量化，在历史场景库中搜索最相似场景，辅助定位。
• 物体抓取 ：将物体视觉特征向量化，快速检索已有操作方案的相似物体，复用策略。
• 人机交互 ：用户指令向量化，在意图库中快速匹配最相近的意图，提高理解准确率。

6

向量数据库选择ANN算法

在实际工程中，常用组合：

• HNSW ：Pinecone、Weaviate 的默认索引
• IVF + PQ ：Milvus 的常用配置，兼顾内存和速度