ANN（Approximate Nearest Neighbor）即近似最近邻搜索，是当前处理大规模高维数据最近邻搜索问题的前沿技术。

核心概念

与传统的精确最近邻搜索（Exact Nearest Neighbor）不同：

  • 精确搜索：保证找到绝对最近的邻居（如暴力搜索、KD树在低维时）
  • 近似搜索：以一定的精度损失换取搜索速度的大幅提升
    如kd树算法[[kd树]]，是精确最近邻搜索

为什么需要ANN？

  1. 维度灾难：在高维空间(通常d>20)中，传统方法效率急剧下降
    • KD树等空间划分方法在高维时可能退化为近似暴力搜索
  2. 数据规模：现代应用常需处理百万/十亿级数据点
    • 精确搜索的O(n)时间复杂度难以承受
  3. 实际需求：许多应用不需要绝对精确的结果
    • 推荐系统、相似图片搜索等场景可以接受近似结果

ANN算法评价指标

评估ANN算法常用：

  • 召回率（Recall）：返回结果中真正最近邻的比例
  • 查询速度：单次查询耗时
  • 构建时间：索引构建时间
  • 内存占用：索引大小

局部敏感哈希(LSH)

  • 原理：将相似的点映射到相同”桶”的概率更高
  • 优点：适用于高维数据，近似最近邻搜索
  • 缺点：需要调参，结果不精确

基于图的算法（当前最先进）

  • HNSW（Hierarchical Navigable Small World）

    • 构建多层图结构，上层是”高速公路”，下层是精细搜索
    • 特点：查询快、内存友好、支持动态更新
    • 代表实现：FAISS中的HNSW实现

  • NSG（Navigating Spreading-out Graph）

    • 构建近似最小生成图