美文网首页
R-tree节点空间重叠(overlapping)的思考

R-tree节点空间重叠(overlapping)的思考

作者: Caucher | 来源:发表于2022-04-02 15:09 被阅读0次

    本文的资料来源于R-tree初代论文
    R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING (1984年SIGMOD)
    做本文的一个动机是,中文互联网上对R-tree结构的介绍不少,但是对其设计原因讲的不多,尤其是对于底层小矩形是如何“排序”,“聚类”的。而这个问题导致了R-tree在兄弟节点所代表的空间上是有重叠的。

    1. R-tree的基本介绍

    • 索引的数据对象未必是一个点,也有可能在高维空间上有面积/体积。

    • R-tree索引的其实是数据对象的MBR。

    • 叶子节点是数据对象MBR的MBR,中间节点是孩子节点MBR的MBR,直至根节点。

    • R-tree的中间节点和叶子节点至少有m条记录,m是不足半满的,这一点弱于B+-tree。

    • 搜索方法:从根节点起,其中所有和query对象有overlap的子树,全都要进行搜索。直到找到所有和query对象有overlap的数据对象

    • 插入方法:

      • 找到对应叶子节点:由于子树的MBR可能都无法完全重叠要插入的数据对象q,因此每次都找和q距离最近的(包含q则距离为0)。距离同样近就选择面积小的。
      • 插入q至叶子节点:有可能造成分裂,后面讲。
      • 树调整:让对应叶子节点的MBR要调整一下,使得能闭包q的范围,相应逐层向上调整。如果有分裂的叶子节点,就让父节点再插入一个entry,也有可能造成父节点继续分裂。
    • 删除方法:不详细介绍了。但是和B-tree是不一样的,不会让小节点和兄弟合并,相反是将其中的数据重新插入,以避免空间分割效果退化。

    image.png

    2. R-tree如何组织空间对象的?

    刚才已经提到,插入时,每次会选择离自己最近的节点路由下去,这意味着距离更近的对象,更有可能在同一个节点。这个近的意思其实是那个节点,能用最小的面积增长,把这个新对象包含在它的MBR里。
    这样,我们可以非常容易举出反例,在R-tree上,两个距离很近的对象在两个不同的节点里。但是这并不影响R-tree整体的结构是完备的,高效的。追求绝对最近不一定有意义。

    3. R-tree为何会产生节点空间重叠?

    这要从R-tree的节点分割策略说起。因为在搜索时,所有产生overlap的区域都要被搜索。因此为了能增强剪枝率,索引包含的总的面积越小越好。分割就是这样的heuristic,目标是使分割后两个节点的总面积最小。这其实在插入时已经体现了,因为其尽可能让节点扩张的面积更小。这样的结果必然是会出现重叠以保证合并面积最小。


    image.png

    要找出绝对最小的两组对象,复杂度太高,原文提了两个启发式的贪婪分割方法。

    【n是叶子节点容量,d是空间对象维度】

    3.1 平方级别算法O(n^2d)

    1. 找到两个对象,如果把它们放进一个组里,浪费空间最多;
    2. 遍历所有剩下的点:计算这个点到两个组产生的扩张面积,选择扩张面积差异最大的那个点。
    3. 把这个点分配到为了包括这个点,扩张面积较小的那个组。
    4. 如果剩下的点全部分配到一个组都不够它半满了,直接全丢到那个组里;否则选下一个点。

    3.2 线性级别算法O(nd)

    和平方级别算法很像,只不过初始点是在各维上贪婪的选择某一维离得最远的两个点。
    选剩下的点时也不做选择了,随机选择,分配到扩张面积更小的那一组。

    4. 问题:重叠区域

    重叠其实是一个很大的麻烦,但是原版R-tree并没有考虑到。一个重要的原因是一旦查询对象和重叠区域有交集,那么多个子树都要同时查询,严重影响剪枝率。因此,后续的方法都着重在改善重叠区域问题。

    4.1 R+-tree

    如果数据对象横跨多个区域,那就在多个区域都存一份,这样就不会在叶子节点之间有overlap。相应的,中间节点之间也没有overlap。
    分裂时,会对叶子节点每个维度扫一遍,尝试在均匀把它们分开,在所有维度上,根据Care的指标为分裂打分,选择最好的

    • 缺点:重复放置了部分数据,节点负载不能被保证半满以上,插入分裂算法复杂一些。

    4.1 R*-tree

    R*-tree修改了分裂算法和路由算法,使得重叠面积也被考虑进代价之中。但显然,R*-tree仍然允许重叠,只不过重叠少了很多。R*-tree被认为是一种经典优化。


    image.png

    具体来说,R*-tree的分裂算法如下,对于一个有M+1条记录的待分裂节点:

    1. 选维度:
      1. 对每个维度,让孩子MBR在这个维度上的值排序,然后在中间选择一个点,将这个节点中的M条记录分成两部分,找到那个“最好的”分割点。由于分裂后需要有平衡性保障(每个节点中至少有m个记录),所以至多有M-2m+2个可能的分割点,即不能让两个子节点的基数差距太极端。
        • 如何判定每个分割点的质量呢?即,如果按此分割点将记录分成两个节点,我们计算两个节点内部的margin area(即被节点所代表的MBR所覆盖,但没有被记录的MBR所覆盖,是无意义的覆盖区域),margin area越小越好。
      2. 最终每个维度都会选出一个最好的分割点,比较各个维度,选出一个最好的作为分裂维度。
    2. 选分割线:
      1. 给定维度之后,与想象中不同的是,不直接使用margin are选出来的最好的分割点直接分布,而是选择使两个子节点overlap-value【重叠区域】最小的分布进行分割。

    相关文章

      网友评论

          本文标题:R-tree节点空间重叠(overlapping)的思考

          本文链接:https://www.haomeiwen.com/subject/vkptsrtx.html