Our*_*ros 1 algorithm spatial kdtree nearest-neighbor r-tree
我在 5 维空间中有大约 10 K 点。我们可以假设点在空间 (0,0,0,0,0) 和 (100,100,100,100,100) 中随机分布。显然，整个数据集可以很容易地驻留在内存中。
我想知道 k 最近邻的哪种算法运行得更快，kd-tree 或 RTree。
虽然我对这两种算法有一些非常高级的想法，但我不确定哪个会运行得更快，以及为什么。如果有的话，我愿意探索其他算法，这些算法可以快速运行。如果可能，请说明为什么算法可以运行得更快。
这取决于各种参数。最重要的是您实现这些算法的能力。
我个人发现批量加载的 R*-trees 对于大数据更快，可能是因为它们有更好的扇出。批量加载的 R 树是一个更公平的比较，因为 kd 树通常是批量加载的（实际上，它们根本不支持增量操作）。
对于小数据，kd-trees 可能会更快，而且它们更容易实现。
对于其他事情，请参考这个较早的问题/答案：