R树的形位多目标结点分裂算法*

薄志成，聂乐魁，孙殿柱，李延瑞

(山东理工大学 机械工程学院, 山东 淄博 255049)

R树的形位多目标结点分裂算法*

薄志成，聂乐魁，孙殿柱，李延瑞

(山东理工大学 机械工程学院, 山东 淄博 255049)

主流R树变体结点分裂目标优化策略仅能以单一的优化目标为主，造成其他优化目标过度忽略。针对这一问题，提出一种R树的形位多目标结点分裂算法。将结点分裂视为多目标优化问题，利用Pareto优化方法求解，其中将候选分裂解的周长之和与重叠度视为多目标优化问题的目标。根据上溢结点子结点位置与形状的多目标优化结果选取分裂轴，从而有效减少候选分裂解个数，提高分裂效率。实验结果证明，与CR树、RR*树算法相比，R树的形位多目标聚类结点分裂算法在R树结点分布与数据分布一致性、构建效率及空间查询等方面均有所改善。

R树；多目标优化；形位分布；聚类

0 引言

动态空间索引结构能够很好地满足曲面重建过程中的空间点、三角面片、分片曲面等数据的动态插入、删除、查询等操作需求，并广泛应用于CAD/CAM、地理信息系统、医学图像分析、古建筑修复等领域[1]。

R树是目前最为流行的动态空间索引结构之一[2-5]，具有许多变体，如R+树、RR*树、CR 树以及CBS树等。R+树[6]将某一特定数据对象存储于多个叶索引结点中，避免了兄弟结点之间的重叠，改善了R树的检索效率。RR*树[7]选取子树时依次以周长增量、重叠度增量为最优选取目标，结点分裂时根据结点包围盒初始中心加权偏移选取最优分裂解，使得数据插入与空间查询效率明显提高。……