Annoy

.. figure:: https://raw.github.com/spotify/annoy/master/ann.png :alt: Annoy 示例 :align: center

.. image:: https://github.com/spotify/annoy/actions/workflows/ci.yml/badge.svg :target: https://github.com/spotify/annoy/actions

Annoy（近似最近邻 Oh Yeah）是一个 C++ 库，并带有 Python 绑定，用于在空间中搜索与给定查询点距离较近的点。它还可以创建大型只读的基于文件的数据结构，这些数据结构会被 mmap <https://en.wikipedia.org/wiki/Mmap>__ 映射到内存中，从而允许多个进程共享同一份数据。

安装

要安装，只需运行 pip install --user annoy，即可从 PyPI <https://pypi.python.org/pypi/annoy>_ 下载最新版本。

对于 C++ 版本，只需克隆仓库并 #include "annoylib.h" 即可。

背景

目前已有其他一些库可以进行最近邻搜索。Annoy 的速度几乎与最快的库相当（见下文），但真正让 Annoy 脱颖而出的是它的另一项特性：它能够 使用静态文件作为索引。具体来说，这意味着你可以 在多个进程之间共享索引。Annoy 还将索引的创建与加载分离，因此你可以将索引以文件形式传递，并快速将其映射到内存中。Annoy 的另一个优点是它会尽量减少内存占用，因此生成的索引文件通常非常小。

这有什么用呢？如果你需要查找最近邻，并且拥有多个 CPU 核心，那么你只需要构建一次索引即可。此外，你还可以将静态索引文件分发到生产环境、Hadoop 作业等场景中使用。任何进程都可以将索引文件通过 mmap 映射到内存中，然后立即进行查询。

我们在 Spotify <http://www.spotify.com/>__ 将其用于音乐推荐。在运行矩阵分解算法后，每个用户或物品都可以表示为 f 维空间中的一个向量。这个库帮助我们搜索相似的用户或物品。我们的高维空间中包含数百万首曲目，因此内存使用是一个首要考虑的问题。

Annoy 是由 Erik Bernhardsson <http://www.erikbern.com>__ 在一次 Hack Week <http://labs.spotify.com/2013/02/15/organizing-a-hack-week/>__ 的几个下午时间里开发出来的。

功能概览

• 欧几里得距离 <https://en.wikipedia.org/wiki/Euclidean_distance>、曼哈顿距离 <https://en.wikipedia.org/wiki/Taxicab_geometry>、余弦距离 <https://en.wikipedia.org/wiki/Cosine_similarity>、汉明距离 <https://en.wikipedia.org/wiki/Hamming_distance> 或者 点积距离 <https://en.wikipedia.org/wiki/Dot_product>__
• 余弦距离等价于归一化向量之间的欧几里得距离 = sqrt(2-2*cos(u, v))
• 如果维度不太高（比如少于 100 维）效果更好，但即使高达 1,000 维也能表现出乎意料地好
• 内存占用小
• 允许多个进程共享内存
• 索引创建与查询分离（一旦树结构建立，就无法再添加新条目）
• 原生支持 Python，已在 2.7、3.6 和 3.7 上测试通过。
• 可以在磁盘上构建索引，从而支持无法完全放入内存的大规模数据集索引（由 Rene Hollander <https://github.com/ReneHollander>__ 贡献）

Python 代码示例

.. code-block:: python

from annoy import AnnoyIndex import random

f = 40 # 将被索引的向量长度

t = AnnoyIndex(f, 'angular') for i in range(1000): v = [random.gauss(0, 1) for z in range(f)] t.add_item(i, v)

t.build(10) # 10 棵树 t.save('test.ann')

...

u = AnnoyIndex(f, 'angular') u.load('test.ann') # 非常快速，直接通过 mmap 映射文件 print(u.get_nns_by_item(0, 1000)) # 找到最接近的 1000 个邻居

目前它只接受整数作为条目的标识符。请注意，它会为 max(id)+1 个条目分配内存，因为它假设你的条目编号是 0 … n-1。如果你需要其他类型的 ID，就需要自己维护一个映射表。

完整的 Python API

• AnnoyIndex(f, metric) 返回一个新的读写索引，存储 f 维的向量。度量方式可以是 "angular"、"euclidean"、"manhattan"、"hamming" 或 "dot"。
• a.add_item(i, v) 添加条目 i（任意非负整数）及其对应的向量 v。注意，它会为 max(i)+1 个条目分配内存。
• a.build(n_trees, n_jobs=-1) 构建包含 n_trees 棵树的森林。树的数量越多，查询精度越高。调用 build 后，将不能再添加新的条目。n_jobs 指定用于构建树的线程数量。n_jobs=-1 表示使用所有可用的 CPU 核心。
• a.save(fn, prefault=False) 将索引保存到磁盘，并加载它（参见下一个函数）。保存后，将不能再添加新的条目。
• a.load(fn, prefault=False) 从磁盘加载（通过 mmap）索引。如果将 prefault 设置为 True，它会预先将整个文件读入内存（使用带有 MAP_POPULATE 标志的 mmap）。默认值为 False。
• a.unload() 卸载索引。
• a.get_nns_by_item(i, n, search_k=-1, include_distances=False) 返回最接近的 n 个条目。查询时会检查最多 search_k 个节点，默认值为 n_trees * n。search_k 提供了运行时的权衡：更高的精度和更快的速度之间的取舍。如果将 include_distances 设置为 True，它将返回一个包含两个列表的元组：第二个列表包含所有对应的距离。
• a.get_nns_by_vector(v, n, search_k=-1, include_distances=False) 类似，但通过向量 v 进行查询。
• a.get_item_vector(i) 返回之前添加的条目 i 的向量。
• a.get_distance(i, j) 返回条目 i 和 j 之间的距离。注意：此方法过去返回的是 平方 距离，但从 2016 年 8 月起已更改为返回实际距离。
• a.get_n_items() 返回索引中的条目总数。
• a.get_n_trees() 返回索引中的树的数量。
• a.on_disk_build(fn) 准备 Annoy 在指定文件中而非内存中构建索引（在添加条目前执行，构建完成后无需保存）。
• a.set_seed(seed) 使用给定的种子初始化随机数生成器。仅在构建树时使用，即只有在添加条目之前才需要设置。调用 a.build(n_trees) 或 a.load(fn) 后将不再生效。

注意事项：

• 对输入值没有进行边界检查，请务必小心。
• Annoy 的角距离实际上是归一化向量之间的欧几里得距离，对于两个向量 u 和 v，其值为 sqrt(2(1-cos(u,v)))

C++ API 非常类似：只需 #include "annoylib.h" 即可访问。

权衡

调整 Annoy 的主要参数只有两个：树的数量 n_trees 和查询时检查的节点数量 search_k。

• n_trees 在构建时指定，会影响构建时间和索引大小。较大的值会提高搜索精度，但也会导致索引变大。
• search_k 在运行时指定，影响搜索性能。较大的值会提高搜索精度，但返回结果所需的时间也会更长。

如果未指定 search_k，它将默认为 n * n_trees，其中 n 是近似最近邻的数量。否则，search_k 和 n_trees 大致是独立的，即在 search_k 保持不变的情况下，n_trees 的值不会影响搜索时间，反之亦然。因此，建议在内存允许的情况下尽可能增大 n_trees；而在查询时间有限的情况下，则应尽可能增大 search_k。

你也可以选择接受较慢的搜索速度，以换取更快的加载速度、更低的内存占用和更少的磁盘 I/O。在支持的平台上，索引会在 load 和 save 时进行预取，从而提前将文件从磁盘读入内存。如果你将 prefault 设置为 False，则会按需从磁盘读取内存映射索引的页面，并将其缓存在内存中，直到完成一次搜索为止。这可能会显著增加首次搜索的时间，但对于内存容量远小于索引大小的系统、对已加载索引执行少量查询的情况，或者索引中大部分区域不太可能与搜索查询相关的情形，这种方式可能更为合适。

它是如何工作的

通过使用随机投影（random projections <http://en.wikipedia.org/wiki/Locality-sensitive_hashing#Random_projection>__）并构建一棵树来实现。在树的每个中间节点上，都会选择一个随机超平面，将空间划分为两个子空间。这个超平面是通过从子集中随机采样两点，并取这两点之间的等距超平面来确定的。

我们重复这一过程 k 次，从而得到一棵森林。k 的具体值需要根据你的需求进行调整，权衡精度和性能之间的折衷。

汉明距离（由 Martin Aumüller <https://github.com/maumueller>__ 贡献）会在底层将数据打包成 64 位整数，并利用内置的位计数原语，因此速度相当快。所有的分割都是轴对齐的。

点积距离（由 Peter Sobot <https://github.com/psobot>__ 和 Pavel Korobov <https://github.com/pkorobov>__ 贡献）使用微软研究院 Bachrach 等人在 2014 年发表的方法，将提供的向量从点积（或“内积”）空间转换为更适合查询的余弦空间：a method by Bachrach et al., at Microsoft Research, published in 2014 <https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/XboxInnerProduct.pdf>__。

更多信息

• Dirk Eddelbuettel <https://github.com/eddelbuettel>__ 提供了 Annoy 的 R 版本 <http://dirk.eddelbuettel.com/code/rcpp.annoy.html>__。
• Andy Sloane <https://github.com/a1k0n>__ 提供了 Annoy 的 Java 版本 <https://github.com/spotify/annoy-java>__，不过目前仅支持余弦距离且为只读模式。
• Pishen Tsai <https://github.com/pishen>__ 提供了 Annoy 的 Scala 封装 <https://github.com/pishen/annoy4s>__，该封装使用 JNA 调用 Annoy 的 C++ 库。
• Atsushi Tatsuma <https://github.com/yoshoku>__ 提供了 Annoy 的 Ruby 绑定 <https://github.com/yoshoku/annoy.rb>__。
• Taneli Leppä <https://github.com/rosmo>__ 提供了 Go 语言的实验性支持 <https://github.com/spotify/annoy/blob/master/README_GO.rst>__。
• Boris Nagaev <https://github.com/starius>__ 编写了 Lua 绑定 <https://github.com/spotify/annoy/blob/master/README_Lua.md>__。
• 在 Spotify Hack Week 2016 的部分时间里（以及之后的一段时间），Jim Kang <https://github.com/jimkang>__ 为 Annoy 编写了 Node.js 绑定 <https://github.com/jimkang/annoy-node>__。
• Min-Seok Kim <https://github.com/mskimm>__ 构建了 Annoy 的 Scala 版本 <https://github.com/mskimm/ann4s>__。
• hanabi1224 <https://github.com/hanabi1224>__ 构建了 Annoy 的只读 Rust 版本 <https://github.com/hanabi1224/RuAnnoy>__，同时还提供了 dotnet、jvm 和 dart 的只读绑定。
• 关于 Annoy 的 纽约机器学习聚会演讲 <http://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup>__。
• Annoy 可以作为 conda 包 <https://anaconda.org/conda-forge/python-annoy>__ 在 Linux、OS X 和 Windows 上使用。
• ann-benchmarks <https://github.com/erikbern/ann-benchmarks>__ 是一个针对多种近似最近邻库的基准测试工具。Annoy 在其中表现相当有竞争力，尤其是在高精度场景下：

.. figure:: https://raw.githubusercontent.com/erikbern/ann-benchmarks/main/results/glove-100-angular.png :alt: ANN 基准测试结果 :align: center :target: https://github.com/erikbern/ann-benchmarks

源代码

整个项目完全用 C++ 编写，并包含一些为了提升性能和减少内存占用而做的优化措施。请务必注意这一点 :)

感谢 Qiang Kou <https://github.com/thirdwing>__ 和 Timothy Riley <https://github.com/tjrileywisc>__ 的努力，代码现在也支持 Windows 系统。

要运行测试，请执行 python setup.py nosetests。测试套件中包含一个从互联网下载的大型真实世界数据集，因此执行起来可能需要几分钟时间。

讨论

欢迎随时在 annoy-user <https://groups.google.com/group/annoy-user>__ 论坛上提出问题或发表评论。我在 Twitter 上的账号是 @fulhack <https://twitter.com/fulhack>__。

Annoy 快速上手指南

Annoy (Approximate Nearest Neighbors Oh Yeah) 是由 Spotify 开源的高性能近似最近邻搜索库。它支持构建基于磁盘的只读索引文件，并通过内存映射（mmap）实现多进程共享，特别适合大规模向量检索场景。

环境准备

• 操作系统：Linux, macOS, Windows
• Python 版本：支持 Python 2.7, 3.6, 3.7 及更高版本
• 依赖：
  • Python 用户：仅需 pip 包管理工具。
  • C++ 用户：需要标准 C++ 编译器。
• 硬件建议：适用于维度小于 100 的场景（最高支持至 1000 维），对内存占用有严格限制的场景尤为适合。

安装步骤

Python 安装

推荐使用国内镜像源加速安装：

pip install --user annoy -i https://pypi.tuna.tsinghua.edu.cn/simple

或者使用官方源：

pip install --user annoy

C++ 集成

无需安装命令，直接克隆仓库并在代码中引入头文件：

#include "annoylib.h"

基本使用

以下是最简单的 Python 使用示例，涵盖索引构建、保存、加载及查询全过程。

1. 构建并保存索引

from annoy import AnnoyIndex
import random

f = 40  # 向量维度

# 创建索引对象，指定维度和距离度量方式 ('angular', 'euclidean', 'manhattan', 'hamming', 'dot')
t = AnnoyIndex(f, 'angular')

# 添加数据项 (id, vector)
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    t.add_item(i, v)

# 构建树森林 (树的数量越多，精度越高，但构建时间和索引体积越大)
t.build(10) 

# 保存到磁盘
t.save('test.ann')

2. 加载索引并查询

from annoy import AnnoyIndex

f = 40
u = AnnoyIndex(f, 'angular')

# 加载索引 (速度极快，底层使用 mmap 映射文件，支持多进程共享)
u.load('test.ann') 

# 查找与 item 0 最近的 1000 个邻居
neighbors = u.get_nns_by_item(0, 1000)
print(neighbors)

# 也可以通过向量直接查询
# query_vector = [...] 
# neighbors = u.get_nns_by_vector(query_vector, 1000)

核心参数说明

• n_trees (构建时)：构建的树的数量。值越大精度越高，但索引文件越大，构建时间越长。建议在内存允许范围内尽可能调大。
• search_k (查询时)：搜索时检查的节点数量。默认值为 n_trees * n (n 为请求返回的邻居数)。值越大精度越高，但查询耗时增加。可根据实时性要求在查询时动态调整。