什么是最好的 R 树变体
what is the best R tree variant
我最近正在阅读有关 R 树及其变体的论文和代码：线性树、二次树、R* 树以及 R 树打包 (STR)。在我看来，不同的技术在树创建、范围搜索和knn搜索的时间复杂度上是不同的。 STR树似乎比其他树更好。然而，这些文件是上个世纪的。我只是想知道近 20 年后，目前最好的 R 树变体是什么？
R*-trees 被证明工作得很好并且继续是 go-to 变体。
Bulk-loading 技术（如 STR）是很好的补充，可以更快（更好）地构建 初始 树，而不是一个一个地插入对象。
所以通常情况下，您需要一个具有 STR 批量加载的 R* 树。
另一个更新的树是 X-tree（也是基于 R-Tree）。
如果您正在寻找一般的空间索引，不仅是 R-Tree，我可以推荐 PH-Tree。它可以轻松地与 R-Tree 矩形或 range-queries 变体竞争，具有很好的 kNN-query 支持（对于 21 维仅比 Cover-Tree 慢 50%），它可以很好地扩展大型 and/or 聚类数据集并且非常 space 高效。最好的可能是它具有出色的更新性能，insert/move/remove 几乎不比查找长。另一个优点是它不需要重新平衡，这意味着不会有超过 2 个节点受到任何更新的影响。
缺点：
- 低维度的实现相当复杂，但如果您对 Java 实现没问题，here is mine。
- 高维的实现不那么复杂，但对于小于 10 维的实现速度较慢，here。
- 它最喜欢集群数据，但对于更均匀分布的数据，性能仍然可以。
我最近正在阅读有关 R 树及其变体的论文和代码：线性树、二次树、R* 树以及 R 树打包 (STR)。在我看来，不同的技术在树创建、范围搜索和knn搜索的时间复杂度上是不同的。 STR树似乎比其他树更好。然而，这些文件是上个世纪的。我只是想知道近 20 年后，目前最好的 R 树变体是什么？
R*-trees 被证明工作得很好并且继续是 go-to 变体。
Bulk-loading 技术（如 STR）是很好的补充，可以更快（更好）地构建 初始 树，而不是一个一个地插入对象。
所以通常情况下，您需要一个具有 STR 批量加载的 R* 树。
另一个更新的树是 X-tree（也是基于 R-Tree）。
如果您正在寻找一般的空间索引，不仅是 R-Tree，我可以推荐 PH-Tree。它可以轻松地与 R-Tree 矩形或 range-queries 变体竞争，具有很好的 kNN-query 支持（对于 21 维仅比 Cover-Tree 慢 50%），它可以很好地扩展大型 and/or 聚类数据集并且非常 space 高效。最好的可能是它具有出色的更新性能，insert/move/remove 几乎不比查找长。另一个优点是它不需要重新平衡，这意味着不会有超过 2 个节点受到任何更新的影响。
缺点：
- 低维度的实现相当复杂，但如果您对 Java 实现没问题，here is mine。
- 高维的实现不那么复杂，但对于小于 10 维的实现速度较慢，here。
- 它最喜欢集群数据，但对于更均匀分布的数据，性能仍然可以。