我正在研究近似最近邻算法。
我最近找到了 Annoy Library这在以合理的速度找到 KNN 方面做得非常出色。 如需更深入的分析，您可以浏览 meetup幻灯片。
在阅读幻灯片和检查源代码后，我看不出为什么该算法比 KD-Tree 更好地处理高维数据。
KD-Tree 是一种出色的 NN 算法，但在高维度上，它的运行时间几乎与蛮力搜索 [O(n^2)] 相同，因此它需要检查许多相邻的叶子。
原因是在高维度下，单位球体的体积会变小(你可以看看 here )。
我在 Annoy 库中发现的唯一区别是空间的划分是通过使用超平面完成的，而不是一次划分一维。
有人分析过这个算法并能解释为什么它比 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对此提供了很好的解释(请参阅论文)。然而，如果维数相对较小，即大约 100，则 FLANN应该也很有趣。 FLANN 比 kd-GeRaF 更老，但对我启发很大。
我没有看到 LSH 如何在 Annoy 中使用，正如评论中所建议的那样，但如果是，那么对于 RKD 森林来说没有问题。
关于algorithm - Annoy 方法的性能与。 KD树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37105782/