R-树结点多目标遗传分裂算法  

Nodes Splitting of R*-Tree Based on Multi-objective Genetic Algorithm

作　　者：孙殿柱[1] 宋洋[1] 刘华东[1] 李延瑞[1] 

机构地区：[1]山东理工大学机械工程学院,淄博255091

出　　处：《计算机辅助设计与图形学学报》2013年第10期1454-1459,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(51075247);山东省自然科学基金(ZR2010EM008)

摘　　要：R*-树可有效地提高散乱点云、网格曲面等数据的处理效率.为提高R*-树结点空间利用率,将结点分裂过程视为多目标优化问题,采用遗传多目标优化求解结点分裂的近似全局最优解集;以结点最小外接矩形的重叠度和体积作为评价标准选取最佳分裂方案,实现R*-树的结点最优分裂.实例结果证明,该算法可实现各类复杂几何对象的R*-树结点分裂问题,并有效地降低R*-树结点分裂的参数依赖性,提高R*-树空间数据的查询效率.The R*-tree can improve the processing efficiency of unorganized point clouds and surface meshes.To increase the space utilization of R*-tree nodes,the node splitting of R*-tree is regarded as a multi-objective optimization problem which can be solved by using the genetic algorithm to obtain the approximate global optimal solution sets.The optimal solution is chosen based on the overlap degree and volume of the nodes' minimal bounding rectangles,and then the best node splitting of R*-tree is achieved.Experiments show that the algorithm can solve the node splitting problems for any complex geometric objects and improve the R*-tree spatial query efficiency with few parameters.

关 键 词：R-树结点分裂 遗传算法 多目标优化 自适应聚类 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]