薄志成，聶樂魁，孫殿柱，李延瑞

(山東理工大學 機械工程學院, 山東 淄博 255049)

R樹的形位多目標結點分裂算法*

薄志成，聶樂魁，孫殿柱，李延瑞

(山東理工大學 機械工程學院, 山東 淄博 255049)

主流R樹變體結點分裂目標優(yōu)化策略僅能以單一的優(yōu)化目標為主，造成其他優(yōu)化目標過度忽略。針對這一問題，提出一種R樹的形位多目標結點分裂算法。將結點分裂視為多目標優(yōu)化問題，利用Pareto優(yōu)化方法求解，其中將候選分裂解的周長之和與重疊度視為多目標優(yōu)化問題的目標。根據(jù)上溢結點子結點位置與形狀的多目標優(yōu)化結果選取分裂軸，從而有效減少候選分裂解個數(shù)，提高分裂效率。實驗結果證明，與CR樹、RR*樹算法相比，R樹的形位多目標聚類結點分裂算法在R樹結點分布與數(shù)據(jù)分布一致性、構建效率及空間查詢等方面均有所改善。

R樹；多目標優(yōu)化；形位分布；聚類

0 引言

動態(tài)空間索引結構能夠很好地滿足曲面重建過程中的空間點、三角面片、分片曲面等數(shù)據(jù)的動態(tài)插入、刪除、查詢等操作需求，并廣泛應用于CAD/CAM、地理信息系統(tǒng)、醫(yī)學圖像分析、古建筑修復等領域[1]。

R樹是目前最為流行的動態(tài)空間索引結構之一[2-5]，具有許多變體，如R+樹、RR*樹、CR 樹以及CBS樹等。R+樹[6]將某一特定數(shù)據(jù)對象存儲于多個葉索引結點中，避免了兄弟結點之間的重疊，改善了R樹的檢索效率。RR*樹[7]選取子樹時依次以周長增量、重疊度增量為最優(yōu)選取目標，結點分裂時根據(jù)結點包圍盒初始中心加權偏移選取最優(yōu)分裂解，使得數(shù)據(jù)插入與空間查詢效率明顯提高。CR樹[8]將傳統(tǒng)的兩簇分裂轉變?yōu)槎啻胤至?，利用k均值聚類算法獲取分裂解，降低了分裂過程中的計算代價，提高了建樹效率。CBS樹[9]分裂結點時，以每個結點包圍盒頂點為分類中心，利用對角頂點聚類實現(xiàn)結點分裂，減少了候選解，提高了建樹效率。上述R樹變體從本質上講，是采用多目標優(yōu)化策略在結點分裂時對R樹結構進行優(yōu)化。該策略能夠在一定程度上改善R樹結構,但采用級聯(lián)的單目標優(yōu)化方法的求解結果可能導致最優(yōu)性只滿足了某個主要目標，而在其他目標上表現(xiàn)很差。

本文對結點分裂的特點進行充分考慮，將結點分裂視為多目標優(yōu)化問題，利用Pareto優(yōu)化方法求解，其中優(yōu)化目標為候選分裂解的空間區(qū)域與空間重疊度。為減少Pareto優(yōu)化方法中的候選分裂解個數(shù)以提高分裂效率，將基于上溢結點子結點形狀與位置的分裂軸多目標優(yōu)化作為前續(xù)優(yōu)化。實驗表明，該算法在R樹結點分布與數(shù)據(jù)分布一致性、構建效率及空間查詢等方面均優(yōu)于CR樹、RR*樹。

1 Pareto優(yōu)化求取結點最優(yōu)分裂解

結點分裂問題可視為一個多目標優(yōu)化問題來解決，主要目標在于保證分裂所得的新結點的結點分裂目標——結點包圍盒空間及結點包圍盒之間的重疊空間均趨于最小化。為便于對結點分裂目標進行最小化優(yōu)化，需對目標進行量化表示，本文選用周長作為衡量因子。

(1)

目前在多目標優(yōu)化問題的求解方法中，Pareto優(yōu)化方法應用最為廣泛[10]。獲取上溢結點F候選分裂解集中Pareto最優(yōu)解集的基本流程如圖1所示，具體步驟如下:

步驟1：初始化候選分裂解集Q←?；

步驟2：將F的子結點按其包圍盒中心點在i軸軸向的分量升序排序，得到子結點序列Si；

步驟3：對Si進行子序列對劃分，要求劃分后的子序列中的結點數(shù)不小于m，m為非根結點中所允許的結點個數(shù)下限值。若設劃分后的子序列對為(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最優(yōu)解集P*，根據(jù)P*獲取Q中Pareto最優(yōu)解集Q*。劣質解定義如下:若?Pj∈P且i≠j使得Pi>Pj成立，其中Pi>Pj表示Φi>Φj且Ψi>Ψj，則Pi為劣質解。

圖1 Pareto最優(yōu)解集獲取流程圖

(2)

(3)

(4)

2 形位多目標選取分裂軸

在結點分裂過程中，上溢結點子結點在軸向的位置分布越離散，即子結點彼此之間相距越遠，則上溢結點按此軸產(chǎn)生的分裂候選解重疊的可能性就越小。為量化表示子結點各軸向的位置分布情況，可將上溢結點F的子結點包圍盒集{fi}轉化為中心點集{ci}，通過ci的方差來衡量。F子結點在j軸軸向的位置分布函數(shù)為:

(5)

當上溢結點中存在狹長子結點包圍盒時，由于狹長包圍盒較長邊的影響，若只利用位置分布函數(shù)選取分裂軸，極易造成后續(xù)產(chǎn)生的分裂解集均具有較大重疊度。為避免狹長包圍盒較長邊的影響，需對包圍盒的形狀進行分析，盡量選取邊長方差較小的軸為分裂軸。利用F子結點在各軸的形狀分布函數(shù)獲取邊長方差較小的軸，其中j軸的形狀分布函數(shù)為:

(6)

基于以上分析，分裂軸應為子結點位置分布函數(shù)值較大且形狀分布函數(shù)值較小的軸，因此可將位置分布函數(shù)與形狀分布函數(shù)視為多目標優(yōu)化問題的兩個目標函數(shù)，并利用Pareto優(yōu)化方法求解。將第1節(jié)的多目標優(yōu)化模型中的Φ、Ψ置換為p、s，鑒于第1節(jié)的多目標優(yōu)化模型為求解多目標的最小值，需將p置換為p的倒數(shù)，則選取分裂軸多目標優(yōu)化問題可用如下數(shù)學模型來描述:

(7)

式中,i表示維度。f(x)值最小的軸即為分裂軸。

3 R樹構建實驗及性能分析

設R樹結點上溢參數(shù)M←30，并根據(jù)文獻[15]的建議設RR*樹的下溢參數(shù)m←0.2M、優(yōu)化因子s←0.5?；贑語言實現(xiàn)相關算法。利用光柵投影式三維測量儀獲取佛像模型表面的采樣點集，獲取的佛像模型點數(shù)為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)佛像點云模型 (點數(shù):108705) (b) CR樹

(c)RR*樹 (d)本文算法構建的R樹圖2 點云數(shù)據(jù)及不同算法內部結點層包圍盒分布

為分析本文結點分裂算法的有效性，分別采用CR樹、RR*樹、本文結點分裂算法為圖2a中的點集構建R樹動態(tài)索引。由于下層結點包圍盒過于狹長極易造成上層結點包圍盒過于龐大，使得結點重疊度增加、查詢效率降低，因此可通過對比內部結點層的構建情況分析三種結點分裂算法的有效性。

對比圖2b、圖2c與圖2d發(fā)現(xiàn): CR樹算法局部出現(xiàn)較大的包圍盒，且在小型空洞處，CR樹與RR*樹算法均出現(xiàn)包圍盒跨越現(xiàn)象，而本文的結點分裂算法使得包圍盒形狀、位置分布與數(shù)據(jù)分布更具一致性。

保持前一實驗R樹參數(shù)不變，分別應用上述三種算法的結點分裂算法對S中數(shù)據(jù)逐一構建R樹，統(tǒng)計建樹時間T1和k近鄰查詢時間T2，T2為點云數(shù)據(jù)中所有數(shù)據(jù)點的k近鄰查詢時間總和，其中k取15。由于CR樹的結點聚類分裂初始聚類中心選取不定，聚類結果會發(fā)生變化，因此需進行多次實驗。本文設定進行7次實驗，T1、T2統(tǒng)計結果分別如圖3、圖4所示。

圖3 R樹構建時間比較

從圖3可知: 相比CR樹算法、RR*樹算法，本文建樹時間T1最小，表明本文結點分裂算法能夠得到較為理想的分裂結果，使得建樹時間減少。并且由圖4可知，利用本文結點分裂算法構建R樹的k近鄰查詢效率較CR樹與RR*樹有所提高。

圖4 k近鄰查詢效率比較

4 結束語

本文對結點分裂的特點進行充分考慮，將結點分裂視為多目標優(yōu)化問題，利用Pareto優(yōu)化方法求解，并基于上溢結點子結點形狀與位置的分裂軸多目標優(yōu)化作為前續(xù)優(yōu)化，結果表明：

(1)形位多目標選取分裂軸使得結點分布與數(shù)據(jù)分布更具一致性，并對候選分裂解集進行了簡化，提高了R樹構建效率，且能夠處理存在狹長包圍盒的情況。

(2)基于Pareto優(yōu)化方法求解結點分裂最優(yōu)解選取問題，使得將周長之和、重疊度能夠并行最優(yōu)，改善了R樹性能，提高了空間近鄰查詢效率。

(3)采用R樹的形位多目標結點分裂算法構建R樹，使得結點分裂更為合理、k近鄰查詢效率有所提高，對提高曲面重建過程中空間點、三角面片、分片曲面等數(shù)據(jù)的處理效率具有重要的意義。

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

[2] 張明波, 陸鋒, 申排偉, 等.R樹家族的演變和發(fā)展[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*-樹結點分裂優(yōu)化算法[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均值聚類優(yōu)化分裂方法[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—)，男，山東沂南人，山東理工大學碩士研究生，研究方向為逆向工程、數(shù)字化設計與制造，(E-mail) bozhicheng91@gmail.com；通訊作者：孫柱殿(1956—)，男，山東煙臺人，山東理工大學教授，博士，研究方向為逆向工程、數(shù)字化設計與制造，(E-mail)dianzhus@sdut.edu.cn。

(編輯李秀敏)