spotify/annoy

## Annoy .. figure:: https://raw.github.com/spotify/annoy/master/ann.png :alt: Annoy example :align: center .. image:: https://github.com/spotify/annoy/actions/workflows/ci.yml/badge.svg :target: https://github.com/spotify/annoy/actions Annoy (`Approximate Nearest Neighbors `__ Oh Yeah) 是一个带有 Python 绑定的 C++ 库，用于搜索空间中距离给定查询点较近的点。它还会创建大型的、基于文件的只读数据结构，这些结构会被 `mmap `__ 映射到内存中，以便让多个进程可以共享相同的数据。 ## 安装 要安装，只需执行 ``pip install --user annoy`` 即可从 `PyPI `_ 下载最新版本。 对于 C++ 版本，只需克隆代码仓库并使用 ``#include "annoylib.h"`` 即可。 ## 背景 还有其他一些用于进行最近邻搜索的库。Annoy 的速度几乎与最快的库一样快（见下文），但实际上还有另一个真正让 Annoy 脱颖而出的功能：它能够**使用静态文件作为索引**。具体来说，这意味着你可以**跨进程共享索引**。Annoy 还将创建索引与加载索引分离开来，因此你可以将索引作为文件进行传递，并快速将它们映射到内存中。Annoy 的另一个优点是它试图最小化内存占用，因此索引非常小。 为什么这很有用？如果你想查找最近邻，并且你有很多 CPU，你只需要构建一次索引。你也可以在生产环境、Hadoop 作业等中传递和分发静态文件。任何进程都能够将索引加载（mmap）到内存中，并立即进行查找。 我们在 `Spotify `__ 使用它来进行音乐推荐。在运行矩阵分解算法之后，每个用户/物品都可以表示为 f 维空间中的一个向量。这个库帮助我们搜索相似的用户/物品。我们在高维空间中有数百万个音轨，因此内存使用是首要考虑的问题。 Annoy 是由 `Erik Bernhardsson `__ 在 `Hack Week `__ 期间的几个下午构建的。 ## 功能摘要 * `欧几里得距离 `__、`曼哈顿距离 `__、`余弦距离 `__、`汉明距离 `__ 或 `点积（内积）距离 `__ * 余弦距离等效于归一化向量的欧几里得距离 = sqrt(2-2*cos(u, v)) * 如果维度不是太多（比如 <100），效果会更好，但即使高达 1,000 个维度，似乎也表现得惊人地好 * 内存占用小 * 允许在多个进程间共享内存 * 索引创建与查找是分开的（特别是，一旦树被创建，就不能再添加更多项目） * 原生 Python 支持，已在 2.7、3.6 和 3.7 版本上测试。 * 在磁盘上构建索引，以便为无法放入内存的大型数据集建立索引（由 `Rene Hollander `__ 贡献） ## Python 代码示例 .. code-block:: python from annoy import AnnoyIndex import random f = 40 # Length of item vector that will be indexed 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 trees t.save('test.ann') # ... u = AnnoyIndex(f, 'angular') u.load('test.ann') # super fast, will just mmap the file print(u.get_nns_by_item(0, 1000)) # will find the 1000 nearest neighbors 目前它只接受整数作为项目的标识符。请注意，它会为 max(id)+1 个项目分配内存，因为它假定你的项目编号为 0 … n-1。如果你需要其他 ID，则必须自己维护一个映射关系。 ## 完整的 Python API * ``AnnoyIndex(f, metric)`` 返回一个新的可读写索引，该索引存储 ``f`` 维的向量。Metric 可以是 ``"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)`` 从磁盘加载（mmaps）索引。如果将 `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 在指定文件中而不是 RAM 中构建索引（在添加项目之前执行，构建后无需保存） * ``a.set_seed(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``，则会根据完成搜索的需要，按需从磁盘读取 mmapped 索引的页面并将其缓存在内存中。这会显著增加早期的搜索时间，但在以下情况下可能更适合：与索引大小相比内存较低的系统、针对已加载索引执行的查询较少，和/或索引的大部分区域与搜索查询无关时。 ## 工作原理 使用 `随机投影 `__ 并构建一棵树。在树的每个中间节点处，选择一个随机超平面，将空间划分为两个子空间。这个超平面是通过从子集中采样两个点并取距离它们等距的超平面来选择的。 我们执行此操作 k 次，以得到一个树的森林。k 必须根据你的需要进行调整，这取决于你在精度和性能之间所做的权衡。 汉明距离（由 `Martin Aumüller `__ 贡献）在底层将数据打包为 64 位整数，并使用内置的位计数原语，因此速度可能相当快。所有的划分都是轴对齐的。 点积距离（由 `Peter Sobot `__ 和 `Pavel Korobov `__ 贡献）使用 `微软研究院的 Bachrach 等人于 2014 年发表的一种方法 `__，将提供的向量从点积（或“内积”）空间转换为更适合查询的余弦空间。 ## 更多信息 * `Dirk Eddelbuettel `__ 提供了 `Annoy 的 R 版本 `__。 * `Andy Sloane `__ 提供了一个 `Annoy 的 Java 版本 `__，尽管目前仅限于余弦且只读。 * `Pishen Tsai `__ 提供了一个 `Annoy 的 Scala 封装 `__，它使用 JNA 调用 Annoy 的 C++ 库。 * `Atsushi Tatsuma `__ 提供了 `Annoy 的 Ruby 绑定 `__。 * `Taneli Leppä `__ 提供了 `对 Go 的实验性支持 `__。 * `Boris Nagaev `__ 编写了 `Lua 绑定 `__。 * 在 Spotify Hack Week 2016 的部分时间（以及之后的一小段时间）里，`Jim Kang `__ 为 Annoy 编写了 `Node 绑定 `__。 * `Min-Seok Kim `__ 构建了 Annoy 的 `Scala 版本 `__。 * `hanabi1224 `__ 构建了 Annoy 的只读 `Rust 版本 `__，以及 **dotnet、jvm 和 dart** 的只读绑定。 * `关于 Annoy 的纽约机器学习聚会演讲 `__ * Annoy 以 `conda 包 `__ 的形式在 Linux、OS X 和 Windows 上提供。 * `ann-benchmarks `__ 是一个针对多个近似最近邻库的基准测试。Annoy 似乎颇具竞争力，尤其是在更高精度下： .. figure:: https://raw.githubusercontent.com/erikbern/ann-benchmarks/main/results/glove-100-angular.png :alt: ANN benchmarks :align: center :target: https://github.com/erikbern/ann-benchmarks ## 源代码 全部使用 C++ 编写，为了性能和内存使用进行了一些不那么优雅的优化。已提前警告过你了 :) 代码应该支持 Windows，这要感谢 `Qiang Kou `__ 和 `Timothy Riley `__。 要运行测试，请执行 `python setup.py nosetests`。测试套件包含一个从互联网下载的大型真实世界数据集，因此执行起来需要几分钟的时间。 ## 讨论 欢迎随时将任何问题或评论发布到 `annoy-user `__ 群组。我在 Twitter 上的账号是 `@fulhack `__。

标签：Apex, C++, Python, 内存映射, 向量检索, 数据擦除, 无后门, 机器学习, 近似最近邻搜索, 逆向工具