scala - 更改 M-tree 中的最大节点容量会影响结果

Question

为这个问题发布整个树的代码是没有意义的（太长而且混乱），我已经尝试解决这个问题一段时间了，所以我真的不想要一些具体的解决方案，但更像是想法为什么会发生这种情况。所以：

• 我有一个 1.000.000 坐标的数据集，我将它们插入到树中。MaxCapacity=10我在得到正确结果之后进行范围搜索（并且对于任何数字> = 10）。如果我切换到MaxCapacity=4结果是错误的。但是，如果我将数据集缩小到大约 20.000 个坐标，结果对于MaxCapacity=4.

所以对我来说，这看起来像是一个不正确的拆分算法，它只显示了我们有大量拆分的小型 MaxCapacities 和大型数据集。但是算法检查了几乎所有的东西，所以我真的找不到那里的错误。还有其他想法吗？树是用 SCALA 编写的，提升策略提升彼此相距最远的两个点，对于拆分策略，我们遍历溢出节点的条目，并将每个条目放入距离较近的提升点的组中。

标签： scalasearchtree

Answer 1

不知道是否有人对此感兴趣，但我找到了造成这种情况的原因。我以为问题出在分裂，但我错了。问题是当我在插入递归算法中选择要跳转到下一个节点以放置条目时。所以我通过计算每个节点的中心和入口点之间的距离来选择这个节点。选择具有最小所述距离的节点。如果条目恰好位于多个节点的半径内，则此方法可以正常工作。在这种情况下， minDistance 按预期工作，但如果条目不位于任何节点的半径中？在这种情况下，我们还必须扩大半径以包含条目。因此，如果要将条目包含在其子节点中，我们将需要找到其半径扩展较小的节点。对于一个节点，它与入口点的距离可能是最小的，但所需的扩展可能是灾难性的。我没有考虑这种情况，结果条目被放置在错误的节点中，导致巨大的扩展，造成巨大的重叠。当我实施这个案例时，问题就解决了！