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]选取子树时依次以周长增量、重叠度增量为最优选取目标，结点分裂时根据结点包围盒初始中心加权偏移选取最优分裂解，使得数据插入与空间查询效率明显提高。CR树[8]将传统的两簇分裂转变为多簇分裂，利用k均值聚类算法获取分裂解，降低了分裂过程中的计算代价，提高了建树效率。CBS树[9]分裂结点时，以每个结点包围盒顶点为分类中心，利用对角顶点聚类实现结点分裂，减少了候选解，提高了建树效率。上述R树变体从本质上讲，是采用多目标优化策略在结点分裂时对R树结构进行优化。该策略能够在一定程度上改善R树结构,但采用级联的单目标优化方法的求解结果可能导致最优性只满足了某个主要目标，而在其他目标上表现很差。

本文对结点分裂的特点进行充分考虑，将结点分裂视为多目标优化问题，利用Pareto优化方法求解，其中优化目标为候选分裂解的空间区域与空间重叠度。为减少Pareto优化方法中的候选分裂解个数以提高分裂效率，将基于上溢结点子结点形状与位置的分裂轴多目标优化作为前续优化。实验表明，该算法在R树结点分布与数据分布一致性、构建效率及空间查询等方面均优于CR树、RR*树。

1 Pareto优化求取结点最优分裂解

结点分裂问题可视为一个多目标优化问题来解决，主要目标在于保证分裂所得的新结点的结点分裂目标——结点包围盒空间及结点包围盒之间的重叠空间均趋于最小化。为便于对结点分裂目标进行最小化优化，需对目标进行量化表示，本文选用周长作为衡量因子。

(1)

目前在多目标优化问题的求解方法中，Pareto优化方法应用最为广泛[10]。获取上溢结点F候选分裂解集中Pareto最优解集的基本流程如图1所示，具体步骤如下:

步骤1：初始化候选分裂解集Q←∅；

步骤2：将F的子结点按其包围盒中心点在i轴轴向的分量升序排序，得到子结点序列Si；

步骤3：对Si进行子序列对划分，要求划分后的子序列中的结点数不小于m，m为非根结点中所允许的结点个数下限值。若设划分后的子序列对为(L，R)，则L∪R=Si，L∩R=∅，将子序列对(L，R)添加到集合Q中；

步骤4：i←i+1，返回步骤2，直至i=n为止，n为F包围盒的维度；

步骤5：求取集合Q中每个候选分裂解的周长之和Φ、重叠度Ψ，得到集合P，其中Pi为(Φi,Ψi)；

步骤6：对P进行Pareto排序，并删除P中的劣质解，继而得到P的Pareto最优解集P*，根据P*获取Q中Pareto最优解集Q*。劣质解定义如下:若∃Pj∈P且i≠j使得Pi>Pj成立，其中Pi>Pj表示Φi>Φj且Ψi>Ψj，则Pi为劣质解。

图1 Pareto最优解集获取流程图

(2)

(3)

(4)

2 形位多目标选取分裂轴

在结点分裂过程中，上溢结点子结点在轴向的位置分布越离散，即子结点彼此之间相距越远，则上溢结点按此轴产生的分裂候选解重叠的可能性就越小。为量化表示子结点各轴向的位置分布情况，可将上溢结点F的子结点包围盒集{fi}转化为中心点集{ci}，通过ci的方差来衡量。F子结点在j轴轴向的位置分布函数为:

(5)

当上溢结点中存在狭长子结点包围盒时，由于狭长包围盒较长边的影响，若只利用位置分布函数选取分裂轴，极易造成后续产生的分裂解集均具有较大重叠度。为避免狭长包围盒较长边的影响，需对包围盒的形状进行分析，尽量选取边长方差较小的轴为分裂轴。利用F子结点在各轴的形状分布函数获取边长方差较小的轴，其中j轴的形状分布函数为:

(6)

基于以上分析，分裂轴应为子结点位置分布函数值较大且形状分布函数值较小的轴，因此可将位置分布函数与形状分布函数视为多目标优化问题的两个目标函数，并利用Pareto优化方法求解。将第1节的多目标优化模型中的Φ、Ψ置换为p、s，鉴于第1节的多目标优化模型为求解多目标的最小值，需将p置换为p的倒数，则选取分裂轴多目标优化问题可用如下数学模型来描述:

(7)

式中,i表示维度。f(x)值最小的轴即为分裂轴。

3 R树构建实验及性能分析

设R树结点上溢参数M←30，并根据文献[15]的建议设RR*树的下溢参数m←0.2M、优化因子s←0.5。基于C语言实现相关算法。利用光栅投影式三维测量仪获取佛像模型表面的采样点集，获取的佛像模型点数为100.1557万个。利用Geomagic Studio对佛像模型采样点集进行随机采样，随机采样因子分别为0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9、1.0，获得10个新点集S={A,B,C,D,E,F,G,H,I,J}，其中点集A如图2a所示。

(a)佛像点云模型 (点数:108705) (b) CR树

(c)RR*树 (d)本文算法构建的R树图2 点云数据及不同算法内部结点层包围盒分布

为分析本文结点分裂算法的有效性，分别采用CR树、RR*树、本文结点分裂算法为图2a中的点集构建R树动态索引。由于下层结点包围盒过于狭长极易造成上层结点包围盒过于庞大，使得结点重叠度增加、查询效率降低，因此可通过对比内部结点层的构建情况分析三种结点分裂算法的有效性。

对比图2b、图2c与图2d发现: CR树算法局部出现较大的包围盒，且在小型空洞处，CR树与RR*树算法均出现包围盒跨越现象，而本文的结点分裂算法使得包围盒形状、位置分布与数据分布更具一致性。

保持前一实验R树参数不变，分别应用上述三种算法的结点分裂算法对S中数据逐一构建R树，统计建树时间T1和k近邻查询时间T2，T2为点云数据中所有数据点的k近邻查询时间总和，其中k取15。由于CR树的结点聚类分裂初始聚类中心选取不定，聚类结果会发生变化，因此需进行多次实验。本文设定进行7次实验，T1、T2统计结果分别如图3、图4所示。

图3 R树构建时间比较

从图3可知: 相比CR树算法、RR*树算法，本文建树时间T1最小，表明本文结点分裂算法能够得到较为理想的分裂结果，使得建树时间减少。并且由图4可知，利用本文结点分裂算法构建R树的k近邻查询效率较CR树与RR*树有所提高。

图4 k近邻查询效率比较

4 结束语

本文对结点分裂的特点进行充分考虑，将结点分裂视为多目标优化问题，利用Pareto优化方法求解，并基于上溢结点子结点形状与位置的分裂轴多目标优化作为前续优化，结果表明：

(1)形位多目标选取分裂轴使得结点分布与数据分布更具一致性，并对候选分裂解集进行了简化，提高了R树构建效率，且能够处理存在狭长包围盒的情况。

(2)基于Pareto优化方法求解结点分裂最优解选取问题，使得将周长之和、重叠度能够并行最优，改善了R树性能，提高了空间近邻查询效率。

(3)采用R树的形位多目标结点分裂算法构建R树，使得结点分裂更为合理、k近邻查询效率有所提高，对提高曲面重建过程中空间点、三角面片、分片曲面等数据的处理效率具有重要的意义。

[1] Eldawy, Mokbel. SpatialHadoop: A MapReduce framework for spatial data[C]//Proceedings of the IEEE International Conference on Data Engineering, 2015.

[2] 张明波, 陆锋, 申排伟, 等.R树家族的演变和发展[J]. 计算机学报, 2005, 28(3):289-300.

[3] Kamel I, Faloutsos C. Hilbert r-tree: An improved r-tree using fractals[C]//VLDB Conference, 1994.

[4] 孙殿柱, 宋洋, 刘华东, 等. 基于均值漂移的 R*-树结点分裂优化算法[J]. 机械工程学报, 2013, 49(13):145-149.

[5] Satoh S, Katayama N. The sr-tree: An index structure for high-dimensional nearest neighbor queries[C]. ACM SIGMOD Record, 1997.

[6] Sellis, Roussopoulos, Faloutsos. The R+-tree: A dynamic index for multi-dimensional objects[J].International Conterence on Very Large Data Bases,1987:507-518.

[7] Beckman N, Seeger B. A revised r*-tree in comparison with related index structures[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, 2009, 799-812.

[8] Theodoridis Y, Brakatsoulas S, Pfoser D. Revisiting r-tree construction principles[C]//Advances in Databases and Information Systems, 2002, 149-162.

[9] Sleit, Al-Nsour. Corner-based splitting: An improved node splitting algorithm for R-tree[J]. Journal of Information Science, 2014, 40(2): 222-236.

[10] Beckman N, Kriegel H, Schneider R, et al. The R*-tree: an efficient and robust access method for points and rectangles[C]//International Conference on Management of data, 1990.

[11] Deb K. Multi-objective optimization using evolutionary algo-rithms[M]. John Wiley & Sons, 2001.

[12] 李延瑞, 孙殿柱, 张英杰,等. R树上溢结点增量式k均值聚类优化分裂方法[J]. 机械工程学报, 2015, 51(19): 131-137.

NodeSplittingofR-treewithFormandPosition,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)

The mainstream methods of node splitting of R-tree are mainly based on single objective optimization, 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 index node and the distribution of data points. The experimental results show that, the R-tree built with the algorithm 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.

R-tree; multi-objective optimization; the distribution of form and position; clustering

TH166;TG502

A

1001-2265(2017)12-0051-03

10.13462/j.cnki.mmtamt.2017.12.012

2017-01-21；

2017-02-22

国家自然科学基金 (51575326)；山东省自然科学基金(ZR2015EM031)

薄志成(1991—)，男，山东沂南人，山东理工大学硕士研究生，研究方向为逆向工程、数字化设计与制造，(E-mail) bozhicheng91@gmail.com；通讯作者：孙柱殿(1956—)，男，山东烟台人，山东理工大学教授，博士，研究方向为逆向工程、数字化设计与制造，(E-mail)dianzhus@sdut.edu.cn。

(编辑李秀敏)