arroy

Arroy (近似最近邻搜索 哈哈) 是一个 Rust 库，具有与 Annoy Python 库 相似的接口，用于在空间中搜索与给定查询向量接近的向量。它基于 LMDB，一个内存映射的键值存储，因此许多进程可以共享相同的数据并以原子方式修改向量。

背景

有一些其他库可以进行最近邻搜索。然而，它们大多数都是内存受限的，并且没有使用 LMDB 作为它们的存储。自 2015 年以来，Annoy 考虑使用 LMDB 作为后端。我们在 LMDB 上构建了 Meilisearch；因此，这是一个明显的选择。由于 Annoy 极大地启发了它，我们受益于相同的低内存占用。

这有什么用？如果您想找到最近邻并且有多个 CPU，您只需要构建一次索引。任何线程都将能够查询基于 LMDB 的索引，并且能够立即进行查找，即使在另一个索引修改它时也是如此。

我们将其用于 Meilisearch 内部。这个库帮助我们的用户搜索相似的文档。我们的用户在高度维度的空间中有数百万个文档（即平均 768，OpenAI 为 1536），因此内存使用是首要考虑的因素。

Arroy 由 @Kerollmops 和 @irevoire 与 @dureuill 的帮助在一周内通过移植 Annoy 的原始 C++ 源代码构建。

功能总结

• 欧几里得距离，曼哈顿距离，余弦距离或点积（内积）距离
• 余弦距离等价于归一化向量的欧几里得距离，即sqrt(2-2*cos(u, v))
• 当维度不是太多（如<100）时效果更好，但似乎在高达1,000维的情况下也能表现出色
• 内存使用量小
• 使用LMDB允许多个进程间共享内存
• 索引创建与查找分开（特别是，一旦创建了树，就不能再添加更多项目）
• 在磁盘上构建索引以使用LMDB索引大数据集（这些数据集无法放入内存）
• 使用rayon进行多线程树构建
• 与Annoy相比，具有更多功能
  • 查询时进行过滤
  • 无需从头开始重建即可增量更新树
  • 使用LMDB原子性地存储和修改不同的索引（索引由u16识别）
  • 在查询时使用LMDB就地修改项目列表
  • 基于LMDB的存储
  • 使用API更安全，即检查维度、距离等
  • 数据库大小不取决于最高项目ID，而是取决于项目数量
  • 适用于您自己的随机数生成器

缺失的功能

• 不支持Python
• 不支持汉明距离
• 由于log(n)查找和非对齐向量（由于LMDB）通常较慢

权衡

调整Arroy需要两个主要参数：树的数量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。

它是如何工作的

使用随机投影并通过构建树来实现。在树的每个中间节点处，选择一个随机超平面，该超平面将空间分成两个子空间。该超平面通过从子集采样两个点并取它们之间的等距超平面来决定。

我们重复执行 k 次这个操作，以便得到一个树丛。k 的值需要根据您对精度和性能之间权衡的需求进行调整。

点积距离（最初由 @psobot 和 @pkorobov 贡献）将提供的向量从点（或“内积”）空间减少到更友好的余弦空间，使用的是 2014 年微软研究院 Bachrach 等人发表的方法。

源代码

所有内容都是用 Rust 编写的，基于 LMDB，没有进行大量不美观的优化以提高性能和内存使用。你已经收到警告了 :)

由于 LMDB 和 Rust 编程语言，代码应该支持 Windows。

非常感谢开源社区

• 感谢 Qdrant 提供的 SIMD 距离函数
• 感谢 Spotify 提供了 Annoy 的原始想法