近似最近邻搜索（APPROXIMATE NEAREST NEIGHBORS，ANN）：
- 在 KNN 最近邻算法 基础上通过近似算法来进行搜索加速
- 通常以牺牲少量精度为代价，实现巨大的速度提升，返回 K 个最近邻
近似最近邻搜索这类算法也被称为快速最大内积搜索（Maximum Inner Product Search，MIPS）算法；得益于 Agent 的发展，目前的很多 MIPS 算法都成为了 RAG 模块的基础设施，也内置在很多主流向量数据库中；而关于不同 MIPS 算法的横向性能测试结果可参考 ANN Benchmarks
LSH
LSH 局部敏感性哈希：引入哈希函数来实现快速的近似距离计算
ANNOY
近似最近邻搜索（APPROXIMATE NEAREST NEIGHBORS OH YEAH，ANNOY）
- 算法过程：（1）利用随机投影构建一组二叉树，每个树的非叶子节点表示一个随机超平面，叶子节点存储一个样本数据点（2）不同的二叉树是独立且随机构建的，每个随机超平面可以将输入空间切分为两个子空间（3）在搜索时迭代每棵树，找到查询向量所在的子空间（4）聚合所有树的结果，给出最终结论
- 算法特点：（1）ANNOY 通过树构建来加速最近邻搜索，实现了模拟哈希函数的效果（2）基于 C++ 的高效近似最近邻算法，针对内存使用和磁盘读写进行了优化
- 算法总结：（1）ANNOY 适用于向量维度<1000，且向量数在百万级的情况（2）生态成熟，上手方便，可扩展性强，支持多种度量距离
HNSW
HNSW（Hierarchical Navigable Small World，2016-03）
- 算法过程：（1）构建多层图，底层包含所有数据点，底层通过采样来组成上层，直到顶层（2）每层数据点之间构建边，来描述样本间的相关性（3）不同层之间的数据点，也会根据相关性预先建立跳转连接（3）实际搜索时，算法会先在顶层进行贪婪搜索（4）找到当前层的局部最小值后，算法会自动跳转到下层，并重复贪婪搜索（5）最后在底层，找到距离最近的邻数据点
- 算法特点：（1）HNSW 使用分层可导航小世界图进行近似最近邻搜索（2）上层作为粗过滤器，提供远距离跳转，以快速接近目标（3）下层则进行细粒度搜索，以获得精准结果
- 算法总结：（1）具有较快的检索速度和较高的召回率（2）需要较高的内存开销来维护图结构
FAISS
FAISS（Facebook AI Similarity Search, 2017-02）
- FAISS 是Facebook AI团队开源的针对聚类和相似性搜索库，为稠密向量提供高效相似度搜索和聚类，支持十亿级别向量的搜索，是目前较为为成熟的近似近邻搜索库
- FAISS 主要依靠三种基础索引类型来加速相似度的搜索过程（1）IndexFlatL2，最简单的索引类型，直接穷举每个查询向量与所有向量的 L2 距离（2）IndexIVFFlat，基于聚类算法对搜索条目分组分桶，先搜索最近簇中心，再搜索最近样本（3）IndexIVFPQ，在 IndexIVFFlat 的基础上将向量切分为多个子向量，再对子向量进行量化压缩，即每个子向量用有限的码表来近似
- 算法总结：（1）IndexFlatL2，结果精准但开销大，适合小数据集（2）IndexIVFFlat，结果相对精准，且搜索快速，需要额外训练聚类模型（3）IndexIVFPQ，存储空间最小，查询效率高，但存在一定的误差和训练成本，需要额外训练聚类模型，适合大规模数据集（十亿级别）
SPTAG
SPATG（Space Partition Tree And Graph, 2019-05）
- 算法细节：（1）SPATG 主要采用的是空间分区树和图索引进行加速检索，可支持服务化和集群化部署（2）空间分区树，是利用 K-Means 聚类后划分出 K 叉树（3）图索引，先快速构建近似 KNN 图，然后根据 RNG Rule 移除不符合要求的边（4）实际搜索时，SPATG 会先根据空间分区树获取“种子”向量，再以此向量为起始点，在 KNN 图中找到近邻数据点
- 算法总结：（1）由 Microsoft Research (MSR) 和 Microsoft Bing 发布的大规模向量 ANN 搜索库（2）
RNG Rule（Relative Neighborhood Graph Rule，相对邻近图准则）：如果 KNN 子图中的三个节点构成了三角形，则删除三角形中的最长的边；该准则对 KNN 子图进行稀疏化处理，减弱短路效应，有助于增强后续算法的稳健性
采用近似 KNN 图的快速构建，来应对样本规模非常大的情况，具体步骤如下：（1）先构建具备一定深度的 TPTree，KDTree的变种（2）围绕 TPTree 的叶子节点对应的子空间，利用暴力穷举法构建 KNN 子图（3）重复以上过程得到 N 个 KNN 子图，然后连接子图实现 KNN 图的近似（4）划分次数 N 越大，近似 KNN 图就越接近真实 KNN 图
ScaNN
ScaNN（Scalable Nearest Neighbors, 2019-08）
- Google 在2020年开源的一种高效的大规模向量相似性搜索方法
- 算法细节：（1）类似于 FAISS，ScaNN 也是一种基于聚类分桶和向量压缩的 IVFPQ 算法（2）ScaNN 引入额外的惩罚来优化量化误差（3）ScaNN 通过聚类来取代之前的量化压缩，每个子向量聚类到 16 个分组，每个簇中心存储只需要 4bit，借此来缓解频繁 IO 导致的内存瓶颈（重要）
- 算法总结：面对大规模的复杂数据集，ScaNN 能在高维空间中高效地找到最相关的向量；截止 2025 年底，ScaNN 在 ANN Benchmarks 上也依然是表现最优秀的 MIPS 算法之一
其他
- QSG-NGT：华为在自家 GaussDB 向量数据库内置的 ANN 算法；凭借软硬件结合的方式，从 2023 年发布至今（2025-11）长期霸榜ANN Benchmarks；可惜不是开源的，不清楚算法细节
- LoRANN（2024-10）：基于降秩回归（Reduced-Rank Regression, RRR）的监督得分，来加速 ANN 的聚类搜索过程；论文宣称最终效果SOTA，超越了 QSG-NGT，代码开源
参考：
知乎 - 近似最近邻搜索算法 ANNOY
FAISS 三种向量检索方式学习
Milvus 官方用户指南 - HNSW 算法说明
基于近邻图的向量搜索 SPTAG
Milvus 官方用户指南 - SCANN 算法说明