Annoy 方法的性能与。 KD树
Performance of Annoy method Vs. KD-Tree
我正在研究近似最近邻算法
我最近发现 Annoy Library 它在以合理的速度找到 KNN 方面做得非常出色。
如需更深入的分析，您可以浏览 meetup 幻灯片。
在阅读幻灯片和检查源代码后，我看不出为什么这个算法比 KD-Tree 更好地处理高维数据。
KD-Tree 是一种很棒的 NN 算法，但是在高维度上它达到了 运行 的时间，这几乎与暴力搜索 [O(n^2)] 相同，因此它需要检查许多相邻的叶子。
原因是在高维度下，单位球体的体积会变小（你可以看看here）。
我在 Annoy 库中发现的唯一区别是 space 的划分是通过使用超平面完成的，而不是一次划分一维。
有人分析过这个算法并能解释为什么它比 KD-Tree 快得多吗？
阅读 Annoy 的这一部分：
How does it work:
Using random projections and by building up a tree. At every
intermediate node in the tree, a random hyperplane is chosen, which
divides the space into two subspaces. This hyperplane is chosen by
sampling two points from the subset and taking the hyperplane
equidistant from them.
We do this k times so that we get a forest of trees. k has to be tuned
to your need, by looking at what tradeoff you have between precision
and performance.
我想这里的关键是树林。您正在与 KD 树进行比较，KD 树是一种相当古老的数据结构，并且正如您所说，遭受维数灾难。
我认为在这里使用随机 KD 树的森林是一个很好的匹配。
例如，我的kd-GeRaF offers a good explanation on this (see the paper). If however the number of dimensions is relatively small, i.e. around 100, then FLANN应该也很有趣。 FLANN 比 kd-GeRaF 更老，但对我启发很大。
我没有看到 LSH 如何在 Annoy 中使用，如评论中所建议的，但如果是，那么对于 RKD 森林来说没问题。
我正在研究近似最近邻算法
我最近发现 Annoy Library 它在以合理的速度找到 KNN 方面做得非常出色。 如需更深入的分析，您可以浏览 meetup 幻灯片。
在阅读幻灯片和检查源代码后，我看不出为什么这个算法比 KD-Tree 更好地处理高维数据。
KD-Tree 是一种很棒的 NN 算法，但是在高维度上它达到了 运行 的时间，这几乎与暴力搜索 [O(n^2)] 相同，因此它需要检查许多相邻的叶子。
原因是在高维度下，单位球体的体积会变小（你可以看看here）。
我在 Annoy 库中发现的唯一区别是 space 的划分是通过使用超平面完成的，而不是一次划分一维。
有人分析过这个算法并能解释为什么它比 KD-Tree 快得多吗？
阅读 Annoy 的这一部分：
How does it work:
Using random projections and by building up a tree. At every intermediate node in the tree, a random hyperplane is chosen, which divides the space into two subspaces. This hyperplane is chosen by sampling two points from the subset and taking the hyperplane equidistant from them.
We do this k times so that we get a forest of trees. k has to be tuned to your need, by looking at what tradeoff you have between precision and performance.
我想这里的关键是树林。您正在与 KD 树进行比较，KD 树是一种相当古老的数据结构，并且正如您所说，遭受维数灾难。
我认为在这里使用随机 KD 树的森林是一个很好的匹配。
例如，我的kd-GeRaF offers a good explanation on this (see the paper). If however the number of dimensions is relatively small, i.e. around 100, then FLANN应该也很有趣。 FLANN 比 kd-GeRaF 更老，但对我启发很大。
我没有看到 LSH 如何在 Annoy 中使用，如评论中所建议的，但如果是，那么对于 RKD 森林来说没问题。