第12期 2017年12月
组合机床与自动化加工技术
Modular Machine Tool & Automatic Manufacturing Technique
文章编号：10012265(2017)12005103
D0I:10.13462/j.cnki.mmtamt.2017.12.012
R树的形位多目标结点分裂算法
薄志成，聂乐魁，孙殿柱，李延瑞
（山东理工大学机械工程学院，山东淄博255049）
No.12 Dec.2017
摘要：主流R树变体结点分裂目标优化策略仅能以单一的优化目标为主，造成其他优化目标过度忽略。针对这一问题，提出一种R树的形位多目标结点分裂算法。将结点分裂视为多目标优化问题，利用Pareto优化方法求解，其中将候选分裂解的周长之和与重叠度视为多目标优化问题的目标。根据上溢结点子结点位置与形状的多目标优化结果选取分裂轴，从而有效减少候选分裂解个数，提高分裂效率。实验结果证明，与CR树、RR*树算法相比,R树的形位多目标聚类结点分裂算法在R树
结点分布与数据分布一致性、构建效率及空间查询等方面均有所改善。关键词：R树；多目标优化；形位分布；聚类
中图分类号：TH166；TG502
文献标识码：A
Node Splitting of R-tree with Form and Position, Multi-objective
BO Zhi-cheng, NIE Le-kui, SUN Dian-zhu, LI Yan-rui
(School of Mechanical Engineering,Shandong University of Technology ,Zibo Shandong 255049,China)
Abstract : The mainstream methods of node splitting of R-tree are mainly based on single objective optimiza-tion, which lead to excessive ignorant of others objective optimization. For this problem, an algorithm of form and position, multiple goals, clustering was proposed. The process of choosing optimum solution in the algorithm of choosing subtree and splitting node can be considered as the multi-objective optimization The decision vector includes perimeter, overlap and increment of both for node bounding box after inserting object. The split axis can be chose with the distribution of form and position of children node in the overflow node along each axial direction, which can improve the consistency between the distribution of the R-tree in-dex node and the distribution of data points. The experimental results show that, the R-tree built with the al-gorithm of form and position, multiple goals, clustering is better than CR-tree and RR*-tree in synthetic
performance in aspects as the distribution of node, the efficiency of building R-tree and spatial query Key words: R-tree; multi-objective optimization; the distribution of form and position; clustering
0引言
动态空间索引结构能够很好地满足曲面重建过程中的空间点、三角面片、分片曲面等数据的动态插人、删除、查询等操作需求，并广泛应用于CAD/CAM、地理信息系统、医学图像分析、古建筑修复等领域"。
R树是目前最为流行的动态空间索引结构之二[2-5],具有许多变体，如R+树、RR*树、CR树以及 CBS树等。R+树[6]将某一特定数据对象存储于多个叶索引结点中，避免了兄弟结点之间的重叠，改善了R 树的检索效率。RR"树[7]选取子树时依次以周长增量、重叠度增量为最优选取目标，结点分裂时根据结点
收稿日期：2017-01-21；修回日期：2017-02-22
包围盒初始中心加权偏移选取最优分裂解，使得数据插入与空间查询效率明显提高。CR树181将传统的两簇分裂转变为多簇分裂，利用k均值聚类算法获取分裂解，降低了分裂过程中的计算代价，提高了建树效率。CBS树[9]分裂结点时，以每个结点包围盒顶点为分类中心，利用对角顶点聚类实现结点分裂，减少了候选解，提高了建树效率。上述R树变体从本质上讲，是采用多目标优化策略在结点分裂时对R树结构进行优化。该策略能够在一定程度上改善R树结构，但采用级联的单标优化方法的求解结果可能导致最优性只满足了某个主要目标，而在其他目标上表现很差。
本文对结点分裂的特点进行充分考虑，将结点分
*基金项目：国家自然科学基金（51575326）；山东省自然科学基金（ZR2015EM031）
作者简介：薄志成（1991一），男，山东沂南人，山东理工大学碳士研究生，研究方向为遂向工程，数字化设计与制造，（E-mail）bxzhicheng91@
gmail.com；通讯作者：孙柱股（1956一），男，山东烟台人，山东理工大学教授，博士，研究方向为逆向工程、数字化设计与制造，（E-mail）万数据sdul.edlu.cn。