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

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

R樹的形位多目標(biāo)結(jié)點(diǎn)分裂算法*

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

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

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

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

0 引言

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

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

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

1 Pareto優(yōu)化求取結(jié)點(diǎn)最優(yōu)分裂解

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

(1)

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

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

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

步驟3：對(duì)Si進(jìn)行子序列對(duì)劃分，要求劃分后的子序列中的結(jié)點(diǎn)數(shù)不小于m，m為非根結(jié)點(diǎn)中所允許的結(jié)點(diǎn)個(gè)數(shù)下限值。若設(shè)劃分后的子序列對(duì)為(L，R)，則L∪R=Si，L∩R=?，將子序列對(duì)(L，R)添加到集合Q中；

步驟4：i←i+1，返回步驟2，直至i=n為止，n為F包圍盒的維度；

步驟5：求取集合Q中每個(gè)候選分裂解的周長(zhǎng)之和Φ、重疊度Ψ，得到集合P，其中Pi為(Φi,Ψi)；

步驟6：對(duì)P進(jìn)行Pareto排序，并刪除P中的劣質(zhì)解，繼而得到P的Pareto最優(yōu)解集P*，根據(jù)P*獲取Q中Pareto最優(yōu)解集Q*。劣質(zhì)解定義如下:若?Pj∈P且i≠j使得Pi>Pj成立，其中Pi>Pj表示Φi>Φj且Ψi>Ψj，則Pi為劣質(zhì)解。

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

(2)

(3)

(4)

2 形位多目標(biāo)選取分裂軸

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

(5)

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

(6)

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

(7)

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

3 R樹構(gòu)建實(shí)驗(yàn)及性能分析

設(shè)R樹結(jié)點(diǎn)上溢參數(shù)M←30，并根據(jù)文獻(xiàn)[15]的建議設(shè)RR*樹的下溢參數(shù)m←0.2M、優(yōu)化因子s←0.5?；贑語言實(shí)現(xiàn)相關(guān)算法。利用光柵投影式三維測(cè)量?jī)x獲取佛像模型表面的采樣點(diǎn)集，獲取的佛像模型點(diǎn)數(shù)為100.1557萬個(gè)。利用Geomagic Studio對(duì)佛像模型采樣點(diǎn)集進(jìn)行隨機(jī)采樣，隨機(jī)采樣因子分別為0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9、1.0，獲得10個(gè)新點(diǎn)集S={A,B,C,D,E,F,G,H,I,J}，其中點(diǎn)集A如圖2a所示。

(a)佛像點(diǎn)云模型 (點(diǎn)數(shù):108705) (b) CR樹

(c)RR*樹 (d)本文算法構(gòu)建的R樹圖2 點(diǎn)云數(shù)據(jù)及不同算法內(nèi)部結(jié)點(diǎn)層包圍盒分布

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

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

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

圖3 R樹構(gòu)建時(shí)間比較

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

圖4 k近鄰查詢效率比較

4 結(jié)束語

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

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

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

(3)采用R樹的形位多目標(biāo)結(jié)點(diǎn)分裂算法構(gòu)建R樹，使得結(jié)點(diǎn)分裂更為合理、k近鄰查詢效率有所提高，對(duì)提高曲面重建過程中空間點(diǎn)、三角面片、分片曲面等數(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]. 計(jì)算機(jī)學(xué)報(bào), 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*-樹結(jié)點(diǎn)分裂優(yōu)化算法[J]. 機(jī)械工程學(xué)報(bào), 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樹上溢結(jié)點(diǎn)增量式k均值聚類優(yōu)化分裂方法[J]. 機(jī)械工程學(xué)報(bào), 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

國(guó)家自然科學(xué)基金 (51575326)；山東省自然科學(xué)基金(ZR2015EM031)

薄志成(1991—)，男，山東沂南人，山東理工大學(xué)碩士研究生，研究方向?yàn)槟嫦蚬こ?、?shù)字化設(shè)計(jì)與制造，(E-mail) bozhicheng91@gmail.com；通訊作者：孫柱殿(1956—)，男，山東煙臺(tái)人，山東理工大學(xué)教授，博士，研究方向?yàn)槟嫦蚬こ?、?shù)字化設(shè)計(jì)與制造，(E-mail)dianzhus@sdut.edu.cn。

(編輯李秀敏)