ANN（近似最近邻）算法主要分为三类技术路线：基于树的方法、哈希方法和图方法，它们在原理、性能及适用场景上有显著差异：

1. 基于树的方法

核心原理：递归划分数据空间形成树状结构（如二叉树或多叉树），通过树遍历快速筛选候选点。
典型算法：

• KD-Tree：按维度交替分割空间，适合低维数据（维度 < 20）。高维时性能退化明显（“维度灾难”）。
• Annoy（Approximate Nearest Neighbors Oh Yeah）：构建多棵二叉树，通过投票机制提升召回率。平衡精度与速度，支持分布式索引（如Spotify推荐系统）。

适用场景：
✅ 低维空间精确搜索（如2D/3D地理位置检索）
✅ 中等规模数据集（百万级）
⚠️ 高维数据效率低，需配合降维技术

2. 哈希方法

核心原理：将高维数据映射为低维二进制编码（哈希桶），相似点落在相同或相邻桶中。
典型算法：

• 局部敏感哈希（LSH）：设计哈希函数使相似点碰撞概率高。内存占用低，但参数调优复杂，召回率不稳定。
• 乘积量化（PQ）：将向量分割为子向量并分别量化，组合码本压缩表示。压缩比高，适合超大向量库（如十亿级图像检索）。

适用场景：
✅ 超大规模高维数据（如图像/视频特征检索）
✅ 资源受限环境（低内存、分布式存储）
⚠️ 二进制编码损失信息，精度略低于图方法

3. 图方法

核心原理：构建近邻图（节点=数据点，边=相似关系），通过图遍历查找最近邻。
典型算法：

• HNSW（Hierarchical Navigable Small World）：多层图结构，高层为“高速路”快速定位，底层精细搜索。查询速度最快，精度接近暴力搜索。
• NSG（Navigating Spreading-out Graph）：优化图连通性，减少冗余边。内存效率更高，适合对内存敏感场景。

适用场景：
✅ 高精度实时检索（推荐系统、语义匹配）
✅ 十亿级高维数据（如OpenAI Embedding检索）
⚠️ 建图时间长，动态更新成本高

对比总结与选型建议

决策参考：

• 需求高精度+低延迟 → 选择 HNSW；
• 数据规模超大规模+内存敏感 → 选择 PQ哈希；
• 维度低于20维 → 选择 KD-Tree。