1 基本概念
1.1 定义与问题描述
近似近邻搜索是指在给定查询对象时，从数据集中快速找出与其距离较近或相似度较高的一组候选对象。与要求严格返回最优结果的精确搜索不同，它允许结果在一定范围内偏离真实最近邻，以换取更高的检索效率。此类方法特别适合数据规模大、维度高、实时性要求强的场景。
1.2 与精确近邻搜索的区别
精确近邻搜索强调结果的完全正确性，通常需要对大量样本逐一计算距离，因此在高维或海量数据环境中计算成本较高。近似近邻搜索则通过索引、剪枝、压缩或启发式遍历等方式减少比较次数，重点在于“足够好”的结果。前者更适合小规模、对准确性要求极高的任务，后者更适合在线系统和大规模检索。
1.3 典型应用场景
近似近邻搜索常见于需要快速匹配相似对象的系统中，例如向量检索、图像搜索、推荐系统以及重复内容识别。其共同特点是：数据量大、查询频繁、结果对时延敏感，且通常不必追求完全穷尽所有候选。
1.3.1 向量检索
向量检索是ANN最典型的应用之一，通常将文本、图片、音频或用户行为表示为高维向量，再根据距离或相似度进行搜索。该技术广泛用于语义搜索、问答检索和相似样本召回。
1.3.2 图像与多媒体搜索
在图像与多媒体检索中，系统会先提取视觉特征或多模态特征，再寻找外观或内容相近的素材。ANN能够显著缩短检索时间，适合图库查询、视频片段匹配和素材推荐等任务。
1.3.3 推荐系统
推荐系统常借助ANN在庞大的物品库中快速寻找与用户兴趣接近的候选内容。这样可以在召回阶段迅速缩小范围，为后续排序模型提供高质量候选集。
1.3.4 去重与相似检测
在文档、图片、商品或日志处理中，ANN可用于发现近似重复项和高度相似样本。它在内容清洗、数据治理和审核辅助中具有较高实用价值。
2 数学基础
2.1 距离与相似度度量
近似近邻搜索依赖度量空间中的距离或相似度定义。不同任务会选用不同的度量方式，常见目标是使“更接近”在数学上具有可计算、可比较的含义。
2.1.1 欧氏距离
欧氏距离衡量两个向量在几何空间中的直线距离，适用于特征尺度较为一致的场景。它直观、常用，但在高维环境中往往不如低维时稳定。
2.1.2 余弦相似度
余弦相似度关注两个向量夹角的大小，常用于文本表示、语义向量和推荐场景。它更强调方向一致性，而不是向量长度本身，因此对归一化后的表示尤为常见。
2.1.3 曼哈顿距离
曼哈顿距离又称L1距离，表示各维度差值绝对值之和。与欧氏距离相比，它对少数维度上的大偏差有不同的敏感性，在某些稀疏表示中也较常见。
2.2 高维空间特性
高维数据往往呈现出与低维直觉不同的性质，这也是ANN需要专门设计算法的根本原因之一。随着维度上升，距离分布、空间密度和邻近关系都会发生显著变化。
2.2.1 维度灾难
维度灾难指的是随着特征维数增加，数据空间急剧膨胀，导致搜索所需计算量和样本需求迅速上升。此时简单的遍历方法难以保持高效率。
2.2.2 距离集中现象
在高维空间中，不同点之间的距离常常趋于接近，最近邻与最远邻之间的差异变小。这会削弱基于距离排序的辨别能力，使索引结构更难发挥作用。
2.3 查询目标与评价指标
ANN系统通常不会只看是否找到了“真正最近”的样本，还会综合考察速度、资源占用与结果质量之间的平衡。评价指标因此具有多维度特征。
2.3.1 召回率
召回率衡量系统找回真实近邻的能力，通常用于评估候选集是否覆盖了目标样本。它越高，说明近似结果越接近精确搜索。
2.3.2 精确率
精确率描述返回结果中真正相关样本所占比例。在近邻检索中，它常用于衡量候选列表的纯度和结果可靠性。
2.3.3 查询延迟
查询延迟是从提交请求到返回结果所消耗的时间，是在线检索系统的重要指标。ANN方法的核心优势之一，就是显著降低这一指标。
2.3.4 吞吐量
吞吐量表示单位时间内系统可处理的查询数量。对于高并发服务而言，吞吐量与延迟一样重要，二者通常需要共同优化。
3 核心算法思想
3.1 基于树结构的方法
树结构方法通过空间划分减少候选范围，适合中低维数据或具有一定几何结构的数据集。其基本思路是借助分割超平面或球形边界快速剪枝。
3.1.1 KD树
KD树按维度递归划分空间，可较快定位某个区域内的候选点。它在低维场景下效果较好，但在高维条件下剪枝能力会明显减弱。
3.1.2 球树
球树用球形包围区域组织数据，适合基于簇结构进行搜索。相比简单的轴向划分，它在某些分布下能更紧凑地覆盖样本。
3.1.3 分层划分策略
分层划分通过多级区域细分逐步缩小搜索空间。该思路常与其他方法结合，以便先粗后细地筛选候选项。
3.2 基于哈希的方法
哈希方法将相似对象映射到相同或相近的桶中，以便快速定位候选集合。它依赖构造对相似性敏感的哈希函数，使近似邻居更有可能落入同一组。
3.2.1 局部敏感哈希
局部敏感哈希通过设计特定哈希函数，使相似向量碰撞概率更高。它是ANN领域中具有代表性的经典方法。
3.2.2 多探测哈希
多探测哈希允许查询时检查多个相邻桶，而不仅限于单一哈希值对应的桶。这样能在保持效率的同时提升召回率。
3.2.3 哈希桶检索
哈希桶检索以桶为单位组织候选集合，查询时优先访问可能相关的桶。其性能取决于哈希函数质量和桶内数据分布。
3.3 基于图结构的方法
图结构方法将样本表示为近邻图，通过在图上搜索找到目标节点。此类方法近年来应用广泛，通常兼具较高召回和较快查询速度。
3.3.1 近邻图构建
近邻图构建旨在为每个节点建立若干相邻连接，使图结构尽量反映样本间的真实关系。图的质量会直接影响后续搜索效果。
3.3.2 贪心搜索
贪心搜索从入口点出发，不断向更接近查询点的方向移动，直到找到局部最优或满足停止条件。它实现简单，且通常具有较低延迟。
3.3.3 分层可导航小世界图
分层可导航小世界图通过多层索引和小世界连接提升可达性与搜索效率。上层用于快速跳转，下层用于精细定位，是高性能ANN系统中常见的图式方案。
3.4 基于量化的方法
量化方法通过压缩向量表示来减少存储和计算开销，适合超大规模索引。它通常以轻微精度损失换取更高的空间效率。
3.4.1 向量量化
向量量化将原始向量映射到有限码本中的代表点。该方式可降低存储成本，并加速距离计算。
3.4.2 乘积量化
乘积量化把向量切分为多个子空间分别编码，从而用较短码字近似原始向量。它在大规模检索中应用很广。
3.4.3 残差量化
残差量化在首次近似后继续编码剩余误差，以进一步提升表示精度。它适合对压缩率与精度同时有较高要求的场景。
4 索引与数据结构
4.1 索引构建流程
ANN系统通常先对原始数据进行整理，再生成适合检索的索引结构。构建过程的质量，往往决定了后续查询性能上限。
4.1.1 数据预处理
数据预处理包括去噪、缺失处理、格式统一和异常样本清理等步骤。良好的预处理有助于减少索引偏差。
4.1.2 特征归一化
特征归一化可使不同维度处于更可比的尺度范围内，避免某些特征因数值过大而主导距离计算。它在向量检索中非常常见。
4.1.3 索引训练
部分ANN方法需要先训练索引参数，例如聚类中心、码本或图结构。训练阶段决定了索引如何划分空间以及如何压缩数据。
4.2 索引存储结构
索引存储结构直接影响系统的读写效率、内存占用与扩展能力。不同算法会采用不同的数据布局。
4.2.1 倒排列表
倒排列表按簇或桶记录成员集合，便于快速定位候选区域。它常见于量化与聚类型索引。
4.2.2 压缩编码
压缩编码用短码表示原始向量，以节省空间并提高缓存友好性。编码越紧凑，往往越有利于大规模部署。
4.2.3 邻接表
邻接表用于记录图中节点之间的连接关系，是图检索方法的基础结构。它有助于快速遍历相邻节点。
4.3 增量更新机制
在线系统中的数据并非静止不变，因此索引需要支持新增、删除和局部调整。更新机制的设计决定了系统能否长期稳定运行。
4.3.1 新增数据插入
新增数据插入要求系统在不显著影响查询性能的前提下接纳新样本。某些索引可以直接插入，另一些则需要重新训练局部结构。
4.3.2 删除与重建
删除操作会带来结构碎片或连接失衡，因此有时需要定期重建索引。重建可恢复性能，但会增加维护成本。
4.3.3 在线维护策略
在线维护策略通常结合增量更新、后台合并和分批重构，以降低停机风险。其目标是在可用性和索引质量之间取得平衡。
5 系统实现
5.1 单机实现
单机系统更易部署和调试，适合中等规模数据与较明确的性能边界。实现重点通常在于内存管理、磁盘访问和缓存命中率。
5.1.1 内存型索引
内存型索引将主要结构放入内存，以获得更快访问速度。其优势是延迟低，但对内存容量要求较高。
5.1.2 磁盘型索引
磁盘型索引用于在内存不足时承载更大规模数据。它依赖顺序读写、预取和块组织来减少I/O开销。
5.1.3 缓存优化
缓存优化包括热数据保留、访问局部性利用和查询结果复用等手段。合理的缓存策略可以显著提升系统稳定性。
5.2 分布式实现
当数据规模继续扩大时，ANN系统常通过分布式架构扩展处理能力。此时关键问题转向分片、通信和结果整合。
5.2.1 数据分片
数据分片将整体样本分配到不同节点，以分担存储和计算压力。分片策略会影响负载均衡和查询效率。
5.2.2 并行查询
并行查询可同时访问多个分片或索引节点，从而缩短整体检索时间。它适用于大规模在线服务。
5.2.3 结果合并
结果合并负责汇总各节点返回的候选集，并根据全局距离排序输出最终结果。该步骤需要处理去重、排序和置信度合成等问题。
5.3 硬件加速
硬件加速通过更高并行度的计算资源提升ANN性能，特别适合密集距离计算和批量查询。
5.3.1 SIMD优化
SIMD优化利用向量化指令并行处理多个数据元素，可加速距离计算和编码比对。它是CPU侧常见的性能优化手段。
5.3.2 GPU加速
GPU加速适合大规模矩阵运算和批处理检索。其优势在于高并行吞吐，但也要关注数据传输成本。
5.3.3 专用加速芯片
专用加速芯片面向特定计算模式进行定制设计，能够在能效比上取得优势。它通常用于对成本和性能都较敏感的场景。
6 性能优化
6.1 参数调优
ANN方法通常包含多个可调参数，不同设置会显著影响召回率、延迟和资源消耗。参数调优往往需要结合数据分布与业务目标反复试验。
6.1.1 候选集大小
候选集大小决定系统在初筛后保留多少对象进入精细排序。集合越大，召回通常越高，但计算开销也会增加。
6.1.2 图遍历深度
图遍历深度影响搜索在图结构中扩展的范围。过浅可能漏掉近邻，过深则会增加查询耗时。
6.1.3 哈希表数量
哈希表数量越多，往往越有利于提高碰撞概率和召回率，但也会增加内存和查询成本。需要根据任务要求进行权衡。
6.2 召回与延迟权衡
高质量ANN系统通常不是单纯追求最高召回，而是根据业务需求在结果质量与响应速度之间寻找平衡点。
6.2.1 高召回策略
高召回策略倾向于扩大候选范围、增加搜索步数或提高冗余覆盖率。它适用于对结果完整性较敏感的应用。
6.2.2 低延迟策略
低延迟策略则强调快速返回，通常会减少遍历深度或压缩检索范围。它更适合实时交互场景。
6.2.3 动态阈值控制
动态阈值控制可根据查询负载、样本难度或当前系统状态调整搜索强度。这样有助于在波动场景下维持稳定体验。
6.3 数据集适配
不同类型的数据对ANN算法的偏好并不相同，因此系统往往需要针对特征稠密度和分布形态进行调整。
6.3.1 稠密向量
稠密向量通常包含较多非零特征，适合使用连续空间中的距离方法。此类数据常见于深度表示和多媒体特征。
6.3.2 稀疏向量
稀疏向量在大部分维度上取零，适合利用压缩存储和稀疏运算。文本检索和部分行为特征常呈现这一特点。
6.3.3 非均匀分布数据
非均匀分布数据会导致某些区域样本密集、某些区域稀疏，从而影响索引平衡性。算法需要通过自适应划分或局部优化来改善效果。
7 评测与基准
7.1 常用公开数据集
ANN研究常借助公开数据集比较不同方法的性能，以获得相对统一的评测环境。数据集通常覆盖图像、文本和通用高维特征等类型。
7.1.1 图像数据集
图像数据集常用于测试视觉向量的相似检索能力。它们有助于观察方法在复杂特征上的表现。
7.1.2 文本向量数据集
文本向量数据集主要用于评估语义搜索和表示匹配能力。此类数据往往更贴近自然语言场景。
7.1.3 通用高维基准集
通用高维基准集为算法比较提供标准化条件，便于衡量不同方法在相同输入上的差异。它们常用于论文和工程测试。
7.2 基准测试方法
基准测试通常从离线和在线两个角度考察ANN系统，并辅以压力测试验证极端条件下的稳定性。
7.2.1 离线评测
离线评测在固定数据集上重复执行查询，便于比较不同参数和算法的稳定表现。它适合基础研究与回归分析。
7.2.2 在线评测
在线评测关注真实服务环境中的响应速度、并发能力和用户体验。其结果更接近实际部署效果。
7.2.3 压力测试
压力测试用于检验系统在高并发、大流量或资源紧张情况下的表现。它能暴露出瓶颈和退化模式。
7.3 指标对比分析
指标对比分析通常将准确性、速度和资源占用放在同一框架下观察，以便寻找更符合场景需求的方案。
7.3.1 准确性对比
准确性对比主要考察召回率和近邻命中情况。不同算法在不同数据集上可能表现差异明显。
7.3.2 速度对比
速度对比关注平均延迟、尾延迟和吞吐能力。它对在线系统选型具有直接参考意义。
7.3.3 资源占用对比
资源占用对比包括内存、磁盘和计算开销等方面。高性能方案未必最节省资源，因此部署前通常需要综合评估。
8 典型应用领域
8.1 搜索引擎
在搜索引擎中，ANN可用于语义召回、相似查询扩展和候选文档筛选。它帮助系统从海量内容中迅速定位相关项。
8.2 机器学习推理
在机器学习推理过程中，ANN常用于快速匹配原型、记忆库或嵌入向量。它能为分类、检索式推理和最近邻预测提供支持。
8.3 内容推荐
内容推荐系统借助ANN从庞大内容库中筛选可能感兴趣的项目。该方法常作为召回层的重要组成部分。
8.4 异常检测
ANN可用于寻找与正常样本差异较大的点，辅助发现异常模式。其适合在特征空间中进行局部相似性比较。
8.5 重复内容识别
重复内容识别通过查找相近样本来发现重复上传、镜像素材或高度相似文本。ANN能够提高大规模比对任务的效率。
9 相关技术与扩展
9.1 向量数据库
向量数据库是一类面向向量存储、索引与检索的系统，通常内置ANN能力。它将检索、更新和过滤能力结合在一起，便于工程落地。
9.2 检索增强生成
检索增强生成将外部检索结果引入生成流程，以提升回答的相关性和信息覆盖度。ANN在其中常承担快速召回候选知识的角色。
9.3 语义表示学习
语义表示学习旨在把文本、图像或其他对象映射到可比较的向量空间。表示质量越好，ANN检索结果通常越稳定。
9.4 多模态检索
多模态检索处理来自文本、图像、音频等不同模态的联合表示。ANN可帮助跨模态匹配与相似内容发现。
9.5 自适应检索策略
自适应检索策略会根据查询难度、系统负载和历史反馈动态调整搜索过程。它有助于在不同场景下维持较好的综合性能。
10 发展历程与趋势
10.1 早期算法阶段
ANN早期研究主要集中于树结构、哈希方法和基础量化技术。此阶段强调理论可行性与基本效率提升。
10.2 工程化加速阶段
随着大规模互联网应用的发展，ANN逐步进入工程化优化阶段。系统开始重视缓存、并行、压缩和硬件协同等实践问题。
10.3 大规模向量检索阶段
在海量向量数据成为常态后，ANN发展重点转向可扩展性、动态更新和分布式部署。图方法、量化方法和混合索引方案都得到了广泛应用。
10.4 未来发展方向
未来ANN的发展可能继续围绕更高召回、更低延迟、更强自适应性以及更好的硬件适配展开。随着多模态与在线智能应用增长，检索系统也将更加注重端到端协同优化。