algorithm - RTree 与 kd-trees 的性能

Question

我在 5 维空间中有大约 10 K 点。我们可以假设这些点在空间 (0,0,0,0,0) 和 (100,100,100,100,100) 中随机分布。显然，整个数据集可以很容易地驻留在内存中。

我想知道 k 最近邻的哪种算法运行得更快，kd-tree 或 RTree。

尽管我对这两种算法有一些非常高级的想法，但我不确定哪个会运行得更快，以及为什么。如果有的话，我愿意探索其他可以快速运行的算法。如果可能，请说明算法运行速度更快的原因。

score 5 · Accepted Answer

这取决于各种参数。最重要的是您实现这些算法的能力。

我个人发现批量加载的 R*-trees 对于大数据更快，可能是因为它们有更好的 fan-out。Bulk-loaded R-trees 是一个更公平的比较，因为 kd-trees 通常是bulk-loaded（事实上，它们根本不支持增量操作）。

对于微小的数据，kd-trees 可能会更快，而且它们实现起来要简单得多。

对于其他事情，请参考这个较早的问题/答案：

1 回答 1