java - K-D Tree vs R-Tree 用于小型动态数据

Question

我已经阅读了一些关于 K-D 树与 R-树的 SO 帖子，但我仍然对我的具体应用有一些疑问。

对于我的 Java 应用程序，我想维护相对较少的空间数据点(几十万个)。关键是数据插入不会批量加载，而是频繁增量插入。我还应该提到，我将对空间域的子区域执行大量周期性范围查询。

我读到 K-D 树通常不支持增量构建，而 R 树更适合这种情况，因为它们保持平衡状态。

但是，在研究了此处建议的解决方案之后: Java commercial-friendly R-tree implementation?

我没有发现这些实现很容易用于返回范围搜索中的点列表。但是，我发现:http://java-ml.sourceforge.net/有一个非常好的 K-D 树实现，它可以快速运行并且在测试点集(~25K)方面优于标准数组存储。此外，我读到 R 树在处理点时会存储冗余信息(因为点是最小值 = 最大值的矩形)。

由于我处理的点数较少，这两种结构之间的差异是否不如我处理存储数百万个点的数据库应用程序重要？

Answer 1

R 树不能存储点是不正确的。它们旨在支持矩形，并且需要在内部节点处支持。但是一个好的实现应该在叶子级别存储点，并且那里的数据容量大约是原来的两倍。

您可以简单地存储点，然后将它们作为最小值=最大值的“矩形”暴露给树管理代码。

您的数据不小。小的就像 100 个对象。对于 100 个对象，R 树没有多大意义，因为它可能只包含一个叶子。为了获得良好的性能，R 树需要良好的扇出。 k-d-tree 总是有一个 2 的扇出；它们是二叉树。在 100k 个对象时，k-d-tree 将非常深。假设您的扇出为 100(对于动态 r 树，那么您应该允许每页最多 200 个对象)，您可以在 3 级树中存储 100 万个点。

我用过 ELKI R*-tree，它真的很快。但它不是商业友好的，除非您获得不同的许可:它是 AGPL-3 许可的，这是一个 copyleft 许可。

此外，该 API 并非专为独立使用而设计。如果您想使用它们，最好的方法是使用完整的 ELKI 框架，而不是试图撕掉 R* 树。

如果您的数据是低维(例如 3 维)并且具有有限边界，请不要低估基于网格的简单方法的性能。特别是对于内存操作。在许多情况下，我什至不会使用八叉树，而只是为我的用例定义最佳网格，然后使用对象列表来实现它。在每个网格单元内按一个坐标排序，以进一步提高性能。