我正在研究近似最近邻算法。
我最近发现了Annoy Library，它在以合理的速度找到 KNN 方面做得非常出色。要进行更深入的分析，您可以浏览聚会幻灯片。
在阅读了幻灯片并检查了源代码之后，我看不出这个算法比 KD-Tree 更好地处理高维数据的原因。
KD-Tree 是一种很棒的 NN 算法，但是在高维中它实现的运行时间几乎与蛮力搜索 [O(n^2)] 相同，因此它需要检查许多相邻的叶子。
原因是在高维中，单位球体的体积变得更小（你可以看看这里）。
我在 Annoy 库中发现的唯一区别是空间的划分是通过使用超平面而不是一次划分一个维度来完成的。
有没有人分析过这个算法并能解释为什么它比 KD-Tree 快得多？
阅读 Annoy 的这一部分：
它是如何工作的：
使用随机投影并建立一棵树。在树中的每个中间节点处，选择一个随机超平面，将空间划分为两个子空间。这个超平面是通过从子集中采样两个点并与它们等距的超平面来选择的。
我们这样做 k 次，这样我们就得到了一片树林。k 必须根据您的需要进行调整，通过查看您在精度和性能之间进行的权衡。
我想这里的关键是森林。您正在与 KD-tree 进行比较，KD-tree 是一种相当古老的数据结构，正如您所说，它遭受维数的诅咒。
我认为在这里使用随机 KD 树的森林将是一个很好的匹配。
例如，我的kd-GeRaF 对此提供了很好的解释（参见论文）。但是，如果维数相对较少，即大约 100，那么FLANN也应该很有趣。FLANN 比 kd-GeRaF 还要老，但给了我很多启发。
正如评论中所建议的那样，我看不到在 Annoy 中如何使用 LSH，但如果是这样，那么对于 RKD 森林来说就没有问题了。