algorithm - 二次分裂和线性分裂的区别

Question

我试图了解 r-tree 的工作原理，并看到有两种类型的拆分：二次和线性。

线性和二次之间实际上有什么区别？在哪种情况下，一个会比另一个更受欢迎？

score 2 · Accepted Answer

两者都是寻找小区域分割的启发式方法。

在二次方中，您选择两个创建尽可能多的空白空间的对象。在线性中，您选择两个相距最远的对象。

Quadratic 提供了更好的分割质量。然而，对于许多实际目的，线性与二次一样简单、快速且良好。

score 2 · Accepted Answer

还有更多变体：穷举搜索、Greenes 拆分、Ang Tan 拆分和 R*-tree 拆分。

所有这些都是在可接受的时间内找到一个好的分割的启发式方法。

在我的实验中，R*-tree 分割效果最好，因为它会产生更多的矩形页面。Ang-Tan 虽然是“线性的”，但生成的切片实际上对大多数查询来说都是一种痛苦。通常，构建/插入的成本并不太重要，但查询才是。

score 2 · Accepted Answer

原始的 R-Tree 论文在第 3.5.2 节和第 3.5.3 节中描述了 PickSeeds 和 LinearPickSeeds 之间的差异，第 4 节中的图表显示了两种算法之间的性能差异。请注意，图 4.2 对 Y 轴使用指数刻度。

我个人将 LinearPickSeeds 用于 R-Tree 具有高“流失”且内存使用不重要的情况，而 QuadraticPickSeeds 用于 R-Tree 相对静态或在有限内存环境中的情况。但这只是经验法则；我没有基准来支持这一点。

3 回答 3