一種基于空間劃分樹裁剪外包框的空間索引方法

熊 偉，李瑞清，陳 犖，曹競(jìng)之，資文杰

(國(guó)防科技大學(xué) 電子科學(xué)學(xué)院，湖南 長(zhǎng)沙 410073)

0 引言

隨著空間數(shù)據(jù)的應(yīng)用日益增長(zhǎng)，以O(shè)racle Spatial、IBM Informix、PostGIS和HyPerSpace為例，主流數(shù)據(jù)庫(kù)系統(tǒng)都具備了空間拓展功能，而實(shí)現(xiàn)空間拓展功能的關(guān)鍵是高效的空間索引。目前大多數(shù)的空間索引方法都是采用空間劃分的思想，其中，應(yīng)用最多的是基于最小外包框(minimum bounding box，MBB)的R樹[1]及其相關(guān)的各類變種樹(如R*樹)。因此，對(duì)最小外包框的改進(jìn)是提高索引效率的重要優(yōu)化方法。

最小外包框是基于1組多維數(shù)據(jù)的最小外包矩形，僅需要存儲(chǔ)2個(gè)多維點(diǎn)就可以用來近似表示從簡(jiǎn)單的點(diǎn)到復(fù)雜的空間形狀。通常，空間中位置相近的對(duì)象會(huì)被存儲(chǔ)在同一個(gè)索引節(jié)點(diǎn)內(nèi)，并且用它們的MBB來表示整個(gè)節(jié)點(diǎn)。這種方法的優(yōu)點(diǎn)主要是：①計(jì)算簡(jiǎn)單，計(jì)算復(fù)雜度為線性，易于計(jì)算MBB與查詢窗口之間是否相交；②存儲(chǔ)空間緊湊，只需要記錄2個(gè)空間中的點(diǎn)。外包框之間的相交判斷是空間索引中至關(guān)重要的一環(huán)，因?yàn)榇蠖鄶?shù)的查詢操作都依賴于這種判斷，例如R樹的構(gòu)建和范圍查詢階段[2]、遍歷樹階段、執(zhí)行空間連接階段[3]等。

空間數(shù)據(jù)的劃分質(zhì)量直接影響到空間索引的查詢效率，而數(shù)據(jù)劃分的質(zhì)量通常依據(jù)MBB之間相互重疊的程度來判定。若MBB之間相交重疊度較高，則直接導(dǎo)致數(shù)據(jù)劃分精度不高，使得查詢時(shí)需要遍歷索引樹中的多個(gè)路徑。冗余的覆蓋面積增加了查詢框與MBB相交的可能性，但與MBB內(nèi)的實(shí)際對(duì)象相交的可能性無關(guān)。

如何最小化MBB的覆蓋范圍相關(guān)學(xué)者在R樹的各種優(yōu)化中已做了充分的研究。針對(duì)MBB，研究者們通過各種多邊形來擬合并且進(jìn)行了比較[4]，甚至采用圓形和圓錐[5]來擬合空間數(shù)據(jù)，但普遍存在如下缺點(diǎn)：①表示的復(fù)雜程度增加；②相交測(cè)試的復(fù)雜性；③突起區(qū)域造成的冗余數(shù)據(jù)空間的下限過高。Sidlauskas等[6]提出了一種裁剪外包框(clipping bounding box，CBB)的方法，針對(duì)R樹結(jié)構(gòu)中的每一個(gè)MBB節(jié)點(diǎn)，多存儲(chǔ)一系列輔助點(diǎn)來記錄冗余空間。該方法不僅巧妙地避免了復(fù)雜的表示方法，也沒有使數(shù)據(jù)的相交計(jì)算復(fù)雜化,且R樹的構(gòu)建方法和結(jié)構(gòu)沒有任何修改，只是額外記錄1組空間數(shù)據(jù)，因此該方法能夠廣泛應(yīng)用于各類基于MBB的空間索引中[7-9]，適用性非常廣泛。

由于基于CBB的空間索引方法在查詢過程中比較了全部的裁剪點(diǎn)，在面對(duì)查詢框覆蓋范圍較大的情況時(shí)，查詢性能較低;且在擴(kuò)展到三維空間索引時(shí)，CBB方法沒有考慮相鄰頂點(diǎn)的情況，裁剪空間并不是最優(yōu)的。因此，對(duì)索引節(jié)點(diǎn)外包框的空間進(jìn)行優(yōu)化裁剪，可以減少查詢過程中不必要的子節(jié)點(diǎn)的計(jì)算量；通過分析時(shí)空維度中查詢框與索引節(jié)點(diǎn)外包框的相交情況，對(duì)查詢中后續(xù)判斷階段的算法進(jìn)行研究，避免冗余的裁剪點(diǎn)比較，進(jìn)一步優(yōu)化基于時(shí)空索引進(jìn)行范圍查詢的查詢效率。

1 IB-CBB索引方法

1.1 CBB方法

裁剪外包框(CBB)方法主要是針對(duì)冗余空間，即MBB中沒有實(shí)際對(duì)象的區(qū)域，如圖1中最小外包框Rectangle中非灰色的區(qū)域。它的核心思想是在索引結(jié)構(gòu)中的每個(gè)葉節(jié)點(diǎn)中多存儲(chǔ)1組輔助點(diǎn)來記錄冗余空間，判斷查詢框與節(jié)點(diǎn)外包框相交情況。若相交，則與輔助點(diǎn)比較，用來判斷查詢框是否與節(jié)點(diǎn)中的真實(shí)數(shù)據(jù)相交，數(shù)據(jù)相交則進(jìn)一步沿子節(jié)點(diǎn)繼續(xù)比較;否則直接停止。

圖1 二維空間的裁剪外包框

該方法與輔助點(diǎn)裁剪掉的空間密切相關(guān)，只有當(dāng)查詢框位于被裁剪的空間中，該方法才有優(yōu)化效果。雖然優(yōu)化過程中增加了輔助點(diǎn)的比較，但減少了后續(xù)的子節(jié)點(diǎn)逐一比較環(huán)節(jié)，降低了計(jì)算量。反之，若查詢框與子節(jié)點(diǎn)(真實(shí)數(shù)據(jù))相交，則增加了冗余的輔助點(diǎn)計(jì)算。

該方法在二維的空間索引中能夠在最大程度上裁剪MBB四周的冗余空間，但在時(shí)空索引和更高維度的索引中，CBB方法表現(xiàn)并沒有那么突出，因?yàn)樵跁r(shí)空維度及以上的高維空間中，CBB方法得出的記錄點(diǎn)并不是各頂點(diǎn)裁剪冗余空間的最優(yōu)解點(diǎn)。計(jì)算輔助點(diǎn)的思想是基于天際線(skyline)中支配(dominate)的概念[7]。

定義1支配和支配的參考點(diǎn)。當(dāng)點(diǎn)p比點(diǎn)q在各方面都更加符合條件時(shí)，則稱p支配了q。

定義2各頂點(diǎn)的天際線點(diǎn)集(skyline points)。對(duì)于某個(gè)頂點(diǎn)，頂點(diǎn)的skyline points是所有不被外包框中任何其他點(diǎn)支配的點(diǎn)的集合。

定義3階梯點(diǎn)集(stairline points)。由skyline points拼接出來的點(diǎn)集。

1.2 CBB方法在多維空間中的優(yōu)化

將CBB方法擴(kuò)展到多維空間，以圖2為例，采用CBB方法對(duì)MBB進(jìn)行裁剪。根據(jù)R100的3個(gè)stairline points，可以明顯看到有些stairline points不是最優(yōu)解，即仍存在能夠裁剪更多空間的點(diǎn)。這是因?yàn)椋?dāng)CBB方法在求某頂點(diǎn)的裁剪點(diǎn)時(shí)，沒有考慮相鄰的3個(gè)頂點(diǎn)。在二維平面的空間索引中，顯然不需要這一步，因?yàn)橐欢ù嬖谝粋€(gè)空間數(shù)據(jù)支配它相鄰的頂點(diǎn)，否則MBB的邊界將會(huì)變得更小。

圖2 三維索引中的裁剪外包框

而在時(shí)空索引中，1個(gè)頂點(diǎn)的相鄰頂點(diǎn)是必須要考慮在內(nèi)的。R100、R101的頂點(diǎn)與其相鄰頂點(diǎn)間沒有任何空間數(shù)據(jù)，該相鄰頂點(diǎn)與其他skyline points生成的點(diǎn)有可能成為裁剪點(diǎn)。

其次，假設(shè)在3維空間中存在許多障礙物點(diǎn)和1個(gè)從原點(diǎn)出發(fā)、同時(shí)向3個(gè)維度的正方向延伸的、不斷膨脹的空間立方體，當(dāng)該空間立方體觸碰到障礙物時(shí)，向該維度方向的擴(kuò)張即停止，但仍可以向其他維度不斷擴(kuò)張，直到3個(gè)維度方向上都遇到障礙物點(diǎn)。簡(jiǎn)單地說，就是在空間中求一個(gè)最大的、且不包含任何障礙物點(diǎn)的立方體。從另一個(gè)角度講，也可以認(rèn)為空間中的1個(gè)障礙物點(diǎn)僅可以阻止空間立方體向1個(gè)維度的擴(kuò)張。

根據(jù)上述分析，CBB方法只用了2個(gè)障礙物點(diǎn)來限制空間立方體，該立方體不是最優(yōu)的，它仍可以向另一個(gè)維度方向繼續(xù)延伸，也就是說，對(duì)于CBB方法求出的點(diǎn)，均可以找到更好的點(diǎn)，使得裁剪的空間更大。

因此，優(yōu)化方法的主要思路是：在高維空間中根據(jù)各頂點(diǎn)方向分別求skyline points。在高維空間中求skyline points的方法很多[10]，但考慮到R樹葉節(jié)點(diǎn)中存儲(chǔ)子節(jié)點(diǎn)數(shù)量不多，可以采用最簡(jiǎn)單的嵌套循環(huán)方法。

該方法分別計(jì)算stairline points，并用skyline points過濾被支配的點(diǎn)，但此時(shí)需要額外的記錄。在skyline points的拼接過程中，根據(jù)拼接點(diǎn)的不同組合情況進(jìn)行擴(kuò)展，具體算法如下。

算法1拓展裁剪點(diǎn)算法。

輸入：skyline pointsSkg(R);

輸出：expand pointsEg(R)。

①foreachSki∈Skg(R)do

②foreachSkj∈Skg(R),j>ido

③lX=Rg(Ski,Skj)∥合并skyline points

④Skg(R)XY,Skg(R)XT∥計(jì)算skyline points

⑤N1，N2∥計(jì)算擴(kuò)展點(diǎn)

⑥Eg(R).append(N1,N2)

⑦Eg(R).distinct∥去重復(fù)

1.3 基于相交的CBB方法

在查詢過程中，能夠優(yōu)化的查詢計(jì)算量趨于一個(gè)固定值，而該值僅與實(shí)驗(yàn)數(shù)據(jù)和空間索引的構(gòu)建方法相關(guān)。當(dāng)查詢外包框越大時(shí)，總體的計(jì)算量越大，輔助點(diǎn)與查詢框比較的計(jì)算次數(shù)越多，而優(yōu)化的計(jì)算量卻保持不變，因此，當(dāng)查詢外包框越大，采用優(yōu)化后的空間索引或時(shí)空索引查詢性能會(huì)越低。

為驗(yàn)證該結(jié)論，將所有矩形對(duì)象在大小和形狀方面變化較大的數(shù)據(jù)集par03上進(jìn)行測(cè)試，分別用R樹方法和通過裁剪外包框優(yōu)化后的CBB方法構(gòu)建索引，并隨機(jī)選取同等級(jí)外包框100 000個(gè)，分別在2個(gè)索引下進(jìn)行查詢，統(tǒng)計(jì)查詢的總時(shí)間。通過修改查詢外包框的大小來改變查詢結(jié)果的數(shù)量級(jí)。當(dāng)擴(kuò)大查詢的范圍時(shí)，空間索引的查詢效率如圖3所示，圖中曲線為CBB方法查詢耗時(shí)與R樹方法查詢耗時(shí)的比值。

圖3 CBB與R樹方法的查詢效率

由圖3可以看出，當(dāng)查詢范圍增大時(shí)，耗時(shí)增加，尤其是當(dāng)查詢外包框所包含的數(shù)據(jù)量超過10 000時(shí)，由于裁剪法中需要將大量輔助的裁剪點(diǎn)與查詢外包框比較，導(dǎo)致查詢效率降低。為解決該問題，本文提出一種基于相交的IB-CBB(intersection based clipping bounding box)查詢優(yōu)化算法。

查詢框與數(shù)據(jù)節(jié)點(diǎn)外包框的相交情況可以分為3種類型：一維相交、二維相交和三維相交。

(1)一維相交。在一維層面上分析2條線段的相交情況，如圖4所示，共有4種結(jié)果：左相交(0)、右相交(1)、被包含(2)和包含(3)。其中，紫色線段表示查詢框，黑色線段表示數(shù)據(jù)節(jié)點(diǎn)外包框，向左為負(fù)方向，向右為正方向。分別用0、1、2、3來表示1個(gè)維度上的4種不同的相交情況。

圖4 一維相交情況

(2)二維相交。由于1個(gè)維度共有4種相交情況，根據(jù)排列組合可知，在二維中存在16種相交情況，如圖5所示。其中，白色區(qū)域?yàn)樽钚⊥獍?Rectangle)，紫色區(qū)域?yàn)椴樵兛?Query)。

圖5 二維相交情況

(3)三維相交。三維相交情況較為復(fù)雜，存在3個(gè)維度，每個(gè)維度4種情況，排列組合共計(jì)64種情況。相交情況如圖6所示，可分為6類。

圖6 三維相交情況

圖6(a)表示查詢立方體僅與節(jié)點(diǎn)立方體的8個(gè)頂點(diǎn)所在角落相交，因此只需要和對(duì)應(yīng)的8個(gè)頂點(diǎn)內(nèi)存儲(chǔ)的輔助裁剪點(diǎn)比較即可。

圖6(b)表示查詢立方體與節(jié)點(diǎn)立方體的12個(gè)棱相交，或貫穿這12個(gè)棱，與棱相鄰的2個(gè)頂點(diǎn)內(nèi)存儲(chǔ)的裁剪點(diǎn)都有可能支配查詢立方體，因此需要將2個(gè)頂點(diǎn)內(nèi)的裁剪點(diǎn)進(jìn)行比較。

圖6(c)表示查詢立方體能夠完全包含節(jié)點(diǎn)立方體的一個(gè)面，故必然和節(jié)點(diǎn)內(nèi)的數(shù)據(jù)相交，因此無須與輔助點(diǎn)進(jìn)行比較，直接進(jìn)入子節(jié)點(diǎn)逐一比較的步驟。

圖6(d)表示查詢立方體與節(jié)點(diǎn)立方體的6個(gè)面相交，或縱向/橫向貫穿這6個(gè)面，在這個(gè)面上的4個(gè)頂點(diǎn)內(nèi)存儲(chǔ)的裁剪點(diǎn)都有可能支配查詢立方體，因此需要將這4個(gè)頂點(diǎn)內(nèi)的裁剪點(diǎn)進(jìn)行比較。

圖6(e)表示節(jié)點(diǎn)立方體極小而查詢立方體很大的情況，一般會(huì)出現(xiàn)在查詢過程的中下層節(jié)點(diǎn)中，此時(shí)節(jié)點(diǎn)立方體完全被查詢立方體包含，該節(jié)點(diǎn)中的所有數(shù)據(jù)必然均屬于查詢結(jié)果，可以直接將其包含的所有葉節(jié)點(diǎn)作為結(jié)果輸出。

圖6(f)表示查詢立方體極小而節(jié)點(diǎn)立方體很大的情況，一般會(huì)出現(xiàn)在查詢過程的上層節(jié)點(diǎn)中，這種情況較為復(fù)雜，只能將各頂點(diǎn)存儲(chǔ)的所有裁剪點(diǎn)與之比較，故需要計(jì)算全部的裁剪點(diǎn)。

算法2相交情況判斷。

輸入：維度數(shù)n，查詢范圍Q.min[n],Q.max[n]，節(jié)點(diǎn)外包框R.min[n],R.max[n]；

輸出：相交結(jié)果IR[n]。

①fori← 0 ton∥每個(gè)維度判斷相交情況

② ifQ.min[i]≤R.min[i]then∥判斷為0或3

③ ifQ.max[i]>R.max[i]then

④IR[i]=0

⑤ elseIR[i]=3

⑥ else ifQ.max[i]

then∥判斷為1或2

⑦IR[i]=2

⑧ elseIR[i]=1

⑨ returnIR[n]∥各維度相交情況結(jié)果

算法2為判斷相交情況的計(jì)算方法。該方法需要輸入維度數(shù)n和查詢框Query及節(jié)點(diǎn)外包框Rectangle的各維度最大/最小值。由于此步驟在判斷查詢框與節(jié)點(diǎn)外包框相交后，故二者一定在每個(gè)維度上均存在一部分相交，可參考一維相交的4種情況。對(duì)于第i個(gè)維度，若Q.min[i]≤R.min[i]且兩者相交，則相交結(jié)果一定為0(左相交)或3(包含)，此時(shí)僅需要進(jìn)一步判斷Q.max[i]與R.max[i]的關(guān)系。若Q.max[i]>R.max[i]，則相交情況為0(左相交)或3(包含);若Q.max[i]

優(yōu)化方法的查詢過程如圖7所示，當(dāng)判斷查詢框與節(jié)點(diǎn)外包框相交后，增加判斷相交情況的步驟。當(dāng)判斷相交結(jié)果為“須計(jì)算”時(shí)，將對(duì)應(yīng)的裁剪點(diǎn)與查詢框進(jìn)行比較，判斷支配關(guān)系；當(dāng)相交結(jié)果為“無須計(jì)算”時(shí)，直接進(jìn)入子節(jié)點(diǎn)逐一比較的步驟，無須與裁剪點(diǎn)進(jìn)行比較計(jì)算；當(dāng)判斷為“直接輸出結(jié)果”時(shí)，無須比較子節(jié)點(diǎn)，直接將該節(jié)點(diǎn)下的所有葉節(jié)點(diǎn)作為結(jié)果輸出。當(dāng)所有節(jié)點(diǎn)計(jì)算完畢時(shí)，查詢結(jié)束。

圖7 IB-CBB算法查詢過程

2 實(shí)驗(yàn)部分

2.1 數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境

所有實(shí)驗(yàn)均使用處理器Intel Xeon 32 core*22.10 GHz、文件系統(tǒng)為XFS、物理內(nèi)存為256 GB服務(wù)器。系統(tǒng)運(yùn)行采用Ubuntu 14.04，代碼使用C++編譯。

針對(duì)時(shí)空索引的裁剪方法，將原方法和改進(jìn)方法進(jìn)行比較，并應(yīng)用于現(xiàn)有的多維索引標(biāo)準(zhǔn)(benchmark)[11]中進(jìn)行驗(yàn)證。本文選擇了3個(gè)不同數(shù)據(jù)分布密度的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)：①abs03，由面積相等的四邊形等距分布生成，這些四邊形在位置和延伸方面略有不同,用于面積相等、均勻分布的空間數(shù)據(jù)測(cè)試；②rea03，包含11 958 999個(gè)點(diǎn)，組成3個(gè)維度的數(shù)據(jù)集，用于多維空間數(shù)據(jù)的測(cè)試；③par03，空間對(duì)象在體積和分布方面均有很大變化，用于體積不相等、分布不均勻的空間數(shù)據(jù)測(cè)試。數(shù)據(jù)集具體描述見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

2.2 裁剪面積結(jié)果

根據(jù)R樹窗口查詢代價(jià)模型[1]，給定高度h，Nl表示第l層節(jié)點(diǎn)數(shù)目，nli表示第l層第i個(gè)節(jié)點(diǎn)，設(shè)xli·yli為nli的最小外包框，則對(duì)于X·Y的窗口查詢，在數(shù)據(jù)空間歸一化后，預(yù)期的磁盤訪問次數(shù)DA為

(1)

若裁剪點(diǎn)對(duì)nli最小外包框的面積優(yōu)化比例為P，而裁剪點(diǎn)對(duì)外包框邊長(zhǎng)沒有影響，則優(yōu)化后，預(yù)期磁盤訪問次數(shù)為

Y+yli·X+X·Y)。

(2)

假設(shè)索引節(jié)點(diǎn)外包框平均邊長(zhǎng)都為e，則可以粗略估計(jì)DAC≈[e2·P+e(X+Y)+X·Y]。若索引節(jié)點(diǎn)的平均邊長(zhǎng)和查詢框邊長(zhǎng)均為數(shù)據(jù)空間范圍的1%，則可以估算DAC/DA=(P+3)/4。當(dāng)P=95%，即裁剪后優(yōu)化冗余空間比例為5%時(shí)，查詢性能提升約為1.25%。

圖8為裁剪空間對(duì)查詢性能的影響。由圖8可以看出，節(jié)點(diǎn)訪問量比值(優(yōu)化后節(jié)點(diǎn)訪問量與優(yōu)化前節(jié)點(diǎn)訪問量的比)越小越好。當(dāng)裁剪冗余空間比例小于5%時(shí)，帶來的節(jié)點(diǎn)訪問量?jī)?yōu)化可以忽略不計(jì)。同時(shí)也可以看出，當(dāng)數(shù)據(jù)集平均邊長(zhǎng)越小，裁剪效果帶來的性能提升也相對(duì)較小。

圖8 裁剪空間對(duì)性能的影響

使用本文方法后裁剪空間效果如圖9所示。橫坐標(biāo)表示每個(gè)節(jié)點(diǎn)的最大輔助點(diǎn)存儲(chǔ)數(shù)量，縱坐標(biāo)表示本文方法裁剪空間占總空間的比例。CORNER和EXPAND分別為本文方法對(duì)CBB方法第1次和第2次優(yōu)化后的裁剪空間占總空間的比例。

實(shí)驗(yàn)對(duì)裁剪點(diǎn)設(shè)定了一個(gè)5%的閾值，即裁剪空間占節(jié)點(diǎn)比例小于5%的點(diǎn)不會(huì)被記錄，因?yàn)椴眉舯壤^小對(duì)于索引性能的提升不明顯，卻占用了存儲(chǔ)空間和計(jì)算量。為了研究存儲(chǔ)輔助點(diǎn)的數(shù)量k與裁剪空間之間的關(guān)系，分別選擇k=1，4，8，16，32進(jìn)行實(shí)驗(yàn)。由圖9可知，當(dāng)存儲(chǔ)點(diǎn)的數(shù)量超過8時(shí)，繼續(xù)增加存儲(chǔ)點(diǎn)對(duì)于裁剪空間的提升不明顯。但是增加輔助點(diǎn)存儲(chǔ)數(shù)量會(huì)直接增加查詢過程中的輔助點(diǎn)比較次數(shù)，因此k值不應(yīng)過大。

如圖9所示，本文方法在時(shí)空索引上的裁剪效果最突出，在空間數(shù)據(jù)形狀、大小和分布3個(gè)特征上，均能夠?qū)r(shí)空索引中的大多數(shù)冗余空間裁剪掉，效果明顯優(yōu)于CBB方法，幾乎達(dá)到了CBB方法裁剪空間的3倍。

圖9 裁剪空間比較

2.3 范圍查詢中的性能提升

本文對(duì)常用的空間范圍查詢性能進(jìn)行了實(shí)驗(yàn)。對(duì)par03數(shù)據(jù)集，查詢不同規(guī)模大小的外包框，對(duì)比IB-CBB方法和R樹方法、R*樹方法的節(jié)點(diǎn)訪問量，如圖10所示。橫坐標(biāo)為每個(gè)節(jié)點(diǎn)存儲(chǔ)的輔助點(diǎn)數(shù)量，縱坐標(biāo)為優(yōu)化后的節(jié)點(diǎn)訪問數(shù)量與R樹方法、R*樹方法節(jié)點(diǎn)訪問量的比值，比值越小說明訪問性能越好。查詢的數(shù)據(jù)集QR0、QR2、QR3來自文獻(xiàn)[11]，分別表示查詢1個(gè)、100個(gè)和1 000個(gè)數(shù)據(jù)的外包框數(shù)據(jù)集。

由圖10可以看出，本文優(yōu)化方法對(duì)范圍查詢的性能有很大的提升。查詢的外包框越小，減少的節(jié)點(diǎn)訪問量越多，甚至在一些情況下可以減少40%的節(jié)點(diǎn)計(jì)算次數(shù)。增加輔助點(diǎn)的存儲(chǔ)數(shù)量亦可以減少節(jié)點(diǎn)的訪問量，但同時(shí)會(huì)增加輔助點(diǎn)的計(jì)算次數(shù)，在一定程度上降低了查詢效率。

圖10 節(jié)點(diǎn)訪問量

2.4 索引優(yōu)化情況對(duì)比

在多維索引上，分別對(duì)數(shù)據(jù)集abs03和par03建立時(shí)空索引，采用R樹建立的時(shí)空索引作為原方法，用裁剪空間拓展后的CBB方法在時(shí)空維度建立時(shí)空索引作為裁剪方法，采用本文IB-CBB方法作為相交情況優(yōu)化方法。

改變查詢框的大小以改變查詢范圍的規(guī)模，以R樹方法的查詢時(shí)間為參照，優(yōu)化拓展后的CBB方法和IB-CBB方法的查詢時(shí)間與R樹方法比值變化趨勢(shì)如圖11所示，其中縱坐標(biāo)為CBB方法和IB-CBB方法查詢耗時(shí)與R樹方法耗時(shí)的比值。當(dāng)查詢范圍較小時(shí)，優(yōu)化拓展后的CBB方法效率仍為最優(yōu)，但I(xiàn)B-CBB方法仍比R樹方法查詢效率高，查詢耗時(shí)為R樹方法的80%;而在查詢范圍較大時(shí)，IB-CBB方法的優(yōu)勢(shì)突出，并且時(shí)空索引下的相交情況優(yōu)化法相較于二維下，性能優(yōu)勢(shì)更加明顯。

圖11 索引性能對(duì)比

3 結(jié)論

本文分析了一種CBB優(yōu)化方法，通過存儲(chǔ)額外的輔助點(diǎn)標(biāo)記外包框角落中的冗余空間，減少查詢過程中不必要的子節(jié)點(diǎn)計(jì)算。將該方法從二維平面的空間索引拓展并應(yīng)用到三維時(shí)空索引中，更符合時(shí)間多版本影像數(shù)據(jù)的時(shí)空特性，并且針對(duì)R樹方法無法在時(shí)空索引中求出最優(yōu)解的問題，通過將輔助裁剪點(diǎn)進(jìn)一步向各維度擴(kuò)展，計(jì)算出裁剪冗余空間的最優(yōu)解，有效減少了查詢過程中的節(jié)點(diǎn)訪問數(shù)量，進(jìn)一步提升了時(shí)空索引的查詢性能。本文構(gòu)建了一種基于相交判斷的裁剪外包框時(shí)空索引，實(shí)驗(yàn)結(jié)果表明，IB-CBB索引方法裁剪索引節(jié)點(diǎn)外包框面積是CBB方法的3倍，減少了40%的節(jié)點(diǎn)計(jì)算，查詢耗時(shí)降低了20%，進(jìn)一步提升了基于空間劃分樹的時(shí)空索引的查詢性能。