Annoy方法与KD-Tree的性能比较

Question

我正在研究近似最近邻算法。

我最近发现了Annoy Library，它在合理的速度内找到KNN做得非常好。 要进行更深入的分析，您可以浏览meetup幻灯片。

阅读幻灯片并检查源代码后，我无法看出为什么这种算法在高维数据中比KD-Tree更有效。

KD-Tree是一个很棒的NN算法，但在高维中，它的运行时间几乎与暴力搜索[O(n^2)]相同，因此需要检查许多相邻叶子节点。

原因是在高维中，单位球体的体积变得更小（您可以在这里查看）。

我在Annoy库中唯一发现的区别是使用超平面而不是逐个维度进行分区。

是否有人分析过这个算法并解释为什么它比KD树快那么多？

- lsxliron

---

我对此不是专家，但Annoy正在使用局部敏感哈希来减少输入空间的维数。关于在较低维度空间中搜索的决策可能会错过实际的最近邻居。这就是为什么它是一种近似方法。很可能它具有与二进制空间分割所得到的较低维度空间相同的时间限制。BSP的性能大致与KD树相同。 - Gene

@Gene 谢谢你的回答。我不认为这是这种情况。Annoy 不是 LSH（即使它使用随机投影）。Annoy 生成一组二叉树，其中每个叶子最多可以有 k 个元素，而 LSH 使用哈希表和签名来查找相似项的候选项。此外，根据源代码，它不使用降维技术。 - lsxliron

嗯...好的。文档中的“工作原理”部分直接引用了LSH。投影就是降维。很抱歉我没能帮上忙。 - Gene

因此需要检查许多相邻的叶子节点。为什么呢？KD树在每一步上将数据分成两个相等的部分。我错了吗？ - canbax

Answer 1

阅读Annoy的这一部分：

它是如何工作的：

使用随机投影和构建树。在树的每个中间节点上，选择一个随机超平面，将空间划分为两个子空间。通过从子集中抽样两个点并取距离它们相等的超平面来选择此超平面。

我们这样做k次，以便获得一片森林。通过查看您在精度和性能之间的权衡来调整k。

关键在于森林。我想在这里与KD树进行比较，后者是一种相当古老的数据结构，并且如您所说，会受到维数诅咒的影响。

我认为在这里使用随机化的KD树森林会很好。

例如，我的kd-GeRaF提供了对此的良好解释（请参见论文）。但是，如果维数相对较小，即约为100，则FLANN也应该很有趣。 FLANN比kd-GeRaF旧，但是让我受益匪浅。

---

我不知道LSH在Annoy中如何使用，正如评论中所建议的那样，但对于RKD森林来说这不是问题。

- gsamaras