Annoy（近似最近邻，哦耶）是一个开源的C++库，带有Python绑定，用于近似最近邻搜索。它由Erik Bernhardsson在Spotify工作期间创建，用于驱动音乐推荐，根据嵌入向量查找相似的曲目或艺术家。Annoy专为大规模、只读数据集设计，以其简单、快速和内存高效而闻名，使其成为需要快速相似性搜索的机器学习应用的热门选择。
该库构建了一个随机投影树森林，其中每棵树使用超平面划分数据空间。在查询时，Annoy遍历多棵树以收集候选点，然后对它们进行评分以返回近似最近邻。这种方法以少量精度换取速度和可扩展性的显著提升，尤其适用于高维向量。Annoy支持多种距离度量，包括欧几里得距离、曼哈顿距离、余弦相似度和点积，并且可以通过绑定从C++、Python和其他语言使用。
历史与发展
Annoy于2013年由当时在Spotify担任工程师的Erik Bernhardsson首次发布。该项目源于处理数百万音频曲目并提供实时推荐的需求。Bernhardsson于2014年将该库开源，并迅速在人工智能社区中获得关注。名称“Annoy”是“近似最近邻，哦耶”的俏皮首字母缩写。该库由Bernhardsson和其他贡献者维护，其最新稳定版本为2023年的1.17.3。它托管在GitHub上，并根据Apache 2.0许可证提供。
技术方法
Annoy的核心算法基于随机投影树。在构建阶段，该库通过沿随机选择的超平面在数据中位数处递归分割数据来创建多棵树。每次分割由当前子集中的两个随机选择点确定，超平面是连接它们的线段的垂直平分线。此过程持续进行，直到每个叶子包含最多指定数量的点（默认10个）。生成的树森林存储在磁盘上，允许内存映射加载，这使得多个进程可以共享同一索引而无需复制内存。
在查询时，Annoy从根到叶子遍历每棵树，收集叶子中的点作为候选。然后，它计算查询点到所有候选的精确距离，并返回前k个最近邻。要搜索的树数量是一个参数，控制速度和精度之间的权衡：更多树产生更好的召回率，但查询更慢。Annoy还支持“search_k”参数，限制访问的节点数量，提供对性能的更精细控制。
使用与集成
Annoy在生产系统中广泛使用，特别是在推荐引擎和信息检索中。在Spotify，它被用于驱动“发现每周”播放列表功能，该功能根据用户收听历史推荐新音乐。该库还用于各种深度学习管道，如图像检索、文档相似性和神经网络嵌入搜索。其简单性和无外部依赖使其易于集成到现有项目中。Annoy提供简单的API：通过添加项目构建索引，然后调用build(n_trees)，对于查询使用get_nns_by_vector或get_nns_by_item。该库还支持增量添加项目，但必须重建索引以纳入新数据。
与其他库的比较
Annoy是几个近似最近邻库之一，每个库各有优势。与FAISS（来自Facebook AI Research）和HNSW（分层可导航小世界图）等库相比，Annoy通常更易于使用，且无需训练阶段。然而，与使用基于图方法的HNSW相比，它在给定速度下可能具有较低的召回率。FAISS提供GPU加速和更高级的索引结构，但更重且更复杂。Annoy的内存映射文件使其特别适合超过RAM的大型数据集，因为它可以按需加载索引。此功能在其他库中较少见，使Annoy成为只读、大规模部署的首选。
影响与遗产
Annoy对相似性搜索领域产生了重大影响，并在众多研究论文中被引用。它启发了其他项目，并被用作基准测试研究中的基线。该库的设计影响了后来在生成式人工智能和大型语言模型应用中的发展，在这些应用中，高效检索相关向量对于语义搜索和记忆增强等任务至关重要。Annoy仍然是人工智能生态系统中的相关工具，其代码库是学习近似最近邻算法的宝贵资源。