基于十六叉樹-多尺度表達R樹的TGIS時空數(shù)據(jù)索引算法

馬 龍 姜 嵐 張正義 程慶榮

1(西安航空學(xué)院經(jīng)濟管理學(xué)院 陜西 西安 710077) 2(西安航空學(xué)院計算機學(xué)院 陜西 西安 710077)

0 引 言

隨著時態(tài)地理信息系統(tǒng)(Time Geographic Information System,TGIS)在現(xiàn)代智能交通、車輛軌跡監(jiān)測和圖像處理等諸多領(lǐng)域的廣泛應(yīng)用，該系統(tǒng)在應(yīng)用過程中產(chǎn)生的數(shù)據(jù)量大，數(shù)據(jù)結(jié)構(gòu)復(fù)雜，數(shù)據(jù)表達形式多樣化，用戶訪問數(shù)據(jù)量大。然而，為了解決多用戶視角下TGIS時空數(shù)據(jù)索引需求，支持多維、多分辨率及多尺度時空數(shù)據(jù)存儲表達與索引問題成為當(dāng)前地理信息科學(xué)研究領(lǐng)域普遍關(guān)注的焦點[1-3]。

多維、多分辨率及多尺度時空數(shù)據(jù)存儲表達與索引處理問題復(fù)雜、技術(shù)難度大、研究范圍廣，但從當(dāng)前研究成果來看，主要從三個方面展開：第一個方面是如何利用分塊或擴展八叉樹存儲方法對多分辨率空間數(shù)據(jù)進行組織管理，其中從八叉樹存儲空間大小角度考慮多分辨率空間數(shù)據(jù)的表達問題較為普遍[4-7]，且表達空間數(shù)據(jù)的結(jié)構(gòu)主要以指針或線性八叉樹數(shù)據(jù)結(jié)構(gòu)為主，但這會造成內(nèi)存資源消耗大、對地理信息系統(tǒng)的硬件資源要求高，特別是三維八叉樹數(shù)據(jù)結(jié)構(gòu)只能對空間數(shù)據(jù)進行有效表達，而對于時間上動態(tài)變化的增量數(shù)據(jù)表達問題卻無法表達和存儲；第二個方面是如何實現(xiàn)多維空間數(shù)據(jù)索引方法，其中主要從三維空間R樹或擴展R樹來表達多維空間數(shù)據(jù)[8-10]，但這類索引方法對于多維時空數(shù)據(jù)時索引效率較低；第三個方面是如何實現(xiàn)多尺度空間數(shù)據(jù)表達、處理與索引問題，其中主要從制圖理論、綜合算法模型和四叉樹索引結(jié)構(gòu)等方法進行研究[11-14]，但這些方法解決多尺度空間數(shù)據(jù)時效率較低，無法滿足多用戶多視角下時態(tài)地理數(shù)據(jù)信息增量索引的需求。因此，如何同時將多維度、多尺度和多分辨率的空間數(shù)據(jù)與時態(tài)數(shù)據(jù)進行有效融合、統(tǒng)一存儲和整體表達，達到TGIS中的時空數(shù)據(jù)動態(tài)索引和按需訪問，解決當(dāng)前TGIS應(yīng)用環(huán)境中的多源時空數(shù)據(jù)的動態(tài)管控問題具有重要的研究意義。

綜上可知，為了實現(xiàn)上述多維度、多尺度和多分辨率時空數(shù)據(jù)的存儲和索引問題，本文利用十六叉樹和多尺度表達的R樹索引結(jié)構(gòu)，構(gòu)建基于四維十六叉樹和多尺度表達R樹的時空索引結(jié)構(gòu)4DHMSR(4D Hex tree & Multi-Scale representation R tree integrated spatiotemporal index)樹，提出多維、多尺度和多分辨率數(shù)據(jù)存儲空間劃分與索引算法，實現(xiàn)TGIS中時空數(shù)據(jù)的統(tǒng)一存儲和索引訪問，提高TGIS在不同應(yīng)用領(lǐng)域中時空數(shù)據(jù)的存儲和索引效率。

1 時空數(shù)據(jù)索引結(jié)構(gòu)分析

1.1 十六叉樹結(jié)構(gòu)

十六叉樹(Hex Tree，HT)結(jié)構(gòu)最早是由Joshi在1988年提出[16]，經(jīng)過不斷的實踐應(yīng)用和優(yōu)化，該方法成為移動對象和TGIS數(shù)據(jù)索引的關(guān)鍵技術(shù)。文獻[7]采用線性十六叉樹結(jié)構(gòu)，解決了礦山GIS時空數(shù)據(jù)模型表達問題，但對于時空數(shù)據(jù)的存儲計算空間較大，無法降低時空數(shù)據(jù)計算量。由此本文作者利用十六叉樹索引結(jié)構(gòu)，將隨時態(tài)變化的空間劃分為諸多相同尺度的塊體單元(時空體元)中的數(shù)據(jù)存儲量進行計算，提出了時空體元編解碼存儲的低計算量優(yōu)化算法，較好地解決了上述占用存儲空間大的問題[17]。實踐證明其對海量多維、多分辨率時空數(shù)據(jù)索引、查詢具有突出的特點，因此利用四維十六叉樹結(jié)構(gòu)建立時空數(shù)據(jù)索引是符合多維度、多分辨率時空數(shù)據(jù)檢索要求。如圖1(a)所示，對目標(biāo)對象進行索引時，分辨率為3，時空位置上的塊體被劃分為3個基本正方體，用十六叉樹結(jié)構(gòu)表示為兩個不同的分支，圖1(b)為十六叉樹體元劃分圖解。本文主要從編碼原理、時空體元劃分和搜索方法三個方面對十六叉結(jié)構(gòu)進行詳細(xì)闡述。

(a) 十六叉樹編碼圖解[7](n=3)

(b) 十六叉樹體元劃分圖解圖1 十六叉樹結(jié)構(gòu)示意圖

十六叉樹的編碼原理：首先，將重要的目標(biāo)節(jié)點用7為基數(shù)來編碼，稱為定位碼，定位碼的位數(shù)表達了分辨率的大小或目標(biāo)的劃分程度，并且根據(jù)定位碼來確定搜索目標(biāo)的坐標(biāo)位置，稱為編碼；其次，根據(jù)目標(biāo)對象的坐標(biāo)位置來確定定位碼，稱為解碼；最后，利用定位碼的編解碼解算規(guī)則，計算出定位碼的具體數(shù)值。其定位碼的計算規(guī)則為：① 給定分辨率，確定坐標(biāo)系統(tǒng)大小和體元編碼的位數(shù)；② 對于整個原始體元編碼按照乙字型方向進行編碼，其方向與選取的四維坐標(biāo)有關(guān)。根據(jù)圖1(a)編碼圖解可知，該索引結(jié)構(gòu)對于空間體元對象標(biāo)識與地理時空坐標(biāo)位置存在嚴(yán)格的對應(yīng)關(guān)系[7]。

十六叉的體元劃分原理與八叉樹的對象劃分原理基本類似，只是八叉樹用于表達三維空間目標(biāo)，而十六叉樹用于表達四維時空目，且所有構(gòu)成八叉樹的規(guī)則均符合十六叉的構(gòu)造原則。十六叉樹體元劃分的基本原理是：構(gòu)造一個正方體區(qū)域，該區(qū)域是包含固定時間段內(nèi)所有空間目標(biāo)的最小邊界，定義為原始體元，將有界的目標(biāo)不斷分解成十六個大小相等的子目標(biāo)，每個子目標(biāo)都有固定的邊界，分解的層級深度與目標(biāo)的表示越精細(xì)，所有最深分解層次上的分支目標(biāo)屬于葉子節(jié)點，它們屬于同一個層次，且達到所需的分辨率要求。分解的結(jié)果類似一棵倒立的層次樹，樹的內(nèi)部節(jié)點上涵蓋十六個孩子節(jié)點[7]。

十六叉樹的搜索原理：每棵十六叉樹是由父節(jié)點和孩子節(jié)點構(gòu)成，每個父節(jié)點涵蓋16個子節(jié)點，葉子節(jié)點對應(yīng)查找表項，子節(jié)點代表讀入的搜索路徑，在十六叉樹搜索法中，首先確定查找表的基地址，然后讀取4 bit的體元，求出基地址和體元的并集，得到當(dāng)前查找節(jié)點的地址，如果此節(jié)點為葉子節(jié)點，則終止搜索過程，否則繼續(xù)搜索，如此遞歸地搜索[18]。

1.2 多尺度表達的R樹

多尺度表達的R樹(Multi Scale represented R Tree，MSR樹)是R樹的一種改進形式，MSR樹是N+1維(N是空間維數(shù)，1是分辨率維度)的R樹，基本思想：首先利用R樹表達實體對象的重要度因子[19]將實體對象進行等級劃分，并將分辨率較低的視圖對象數(shù)據(jù)刪除，且在對象表達過程中引入顯示分辨率維，利用MSR樹的深度遍歷層次的樹型來表達多尺度空間數(shù)據(jù)的變化分辨率；其次使用MSR樹的上層樹形結(jié)構(gòu)來表達空間實體對象；最后為了使實際地理空間特征與所表達的樹形分支結(jié)果相符合，需考慮地理空間對象間的關(guān)聯(lián)性，這樣采用綜合算法來實現(xiàn)多尺度空間數(shù)據(jù)索引問題[20]。

根據(jù)圖2(a)中MSR樹的矩形分塊可以看出，在樹形分支R12中的空間對象要素A與樹形分支R16中的空間對象要素B均屬于樹形分支R6。首先，根據(jù)MSR樹的基本思想，為了使實際地理空間特征與所表達的樹形分支結(jié)果相符合，需考慮到地理空間對象要素之間的關(guān)聯(lián)關(guān)系、要素與周圍環(huán)境的語義關(guān)系，這樣可使用綜合算法將空間對象要素A和B進行合并操作。然后，利用空間對象要素的分裂算法，將樹形分支R6進行分裂成孩子節(jié)點，并利用插入算法將樹形分支R12插入R6分支節(jié)點內(nèi)，這樣可完成空間對象要素A和B的合并操作。圖2(b)中的R12與R16雖然被調(diào)整到同一個分支下面，但是前期的插入、劃分和整合過程的時空復(fù)雜度依然沒有降低。

(a) MSR樹矩形分塊結(jié)果

(b) MSR樹結(jié)構(gòu)圖2 MSR樹的基本結(jié)構(gòu)[19]

2 4DHMSR樹

2.1 算法思路和多尺度表達的時空索引方法

根據(jù)上述MSR樹本身存在的問題可知，索引方法通常受到創(chuàng)建效率、存儲空間、索引時間等多種指標(biāo)的影響[10]。為了滿足時空對象增量數(shù)據(jù)索引的要求，采用4DHMSR樹構(gòu)建時空數(shù)據(jù)多尺度索引和查詢方法。4DHMSR樹數(shù)據(jù)結(jié)構(gòu)采用嵌套的二級索引組織形式，其中MR樹為一級索引結(jié)構(gòu)，四維十六叉樹為二級數(shù)據(jù)結(jié)構(gòu)。該嵌套樹形結(jié)構(gòu)既可充分利用十六叉樹快速收斂和劃分特性，也具有MSR樹在多維空間中的高效檢索特性。圖3是4DHMSR樹數(shù)據(jù)結(jié)構(gòu)的組織結(jié)構(gòu)圖。

圖3 4DHMSR樹數(shù)據(jù)結(jié)構(gòu)的組織結(jié)構(gòu)[19]

4DHMSR樹的基本原理：將空間對象按照空間認(rèn)知的方法劃分為n個不同分辨率的子視圖V1,V2,…,Vn，則構(gòu)成圖3所示的時空數(shù)據(jù)多尺度索引的坐標(biāo)軸，其中V1,V2,…,Vn分別用分辨率軸上的一個坐標(biāo)點進行刻畫，坐標(biāo)點的位置由具有Vi分辨率時空對象的最深層次節(jié)點確定。當(dāng)時空對象的現(xiàn)時分辨率介于{Vi,Vj}時，則Vi,Vj之間某一節(jié)點單元可直接指向時空目標(biāo)對象，當(dāng)要查詢某目標(biāo)區(qū)域S內(nèi)分辨率為Vj的子視圖時，只需對存儲在十六叉樹中小于等于Vj分辨率的空間對象和Vj+1的綜合索引結(jié)果進行直接查詢；其次對子MSR樹的搜索對象和時空對象節(jié)點的位置以及Vj深度子樹的查詢進行索引。其具體的索引流程如圖4所示。

圖4 4DHMSR樹多尺度索引流程圖

在4DHMSR樹中，MSR樹是一個N+1維(N是空間維數(shù)，1是多分辨率維)的多尺度表達的時空R樹(Spatiotemporal Tree Multi-Scale Representation，STMSR)附件時間屬性特征的樹形結(jié)構(gòu)，STMSR樹節(jié)點最小包圍盒(Minimal Bounding Rectangle,MBR)是其孩子節(jié)點Childi集合的時空坐標(biāo)軸最小范圍，以秒為時間單位。目標(biāo)索引節(jié)點打包作為STMSR樹的葉子節(jié)點，將其索引項插入葉子節(jié)點的上一層中，利用節(jié)點選擇和節(jié)點分裂子算法優(yōu)化STMSR樹結(jié)構(gòu)。由于采用STMSR樹對某個時間段內(nèi)目標(biāo)對象的空間位置的搜索效率較低，為此，將目標(biāo)對象標(biāo)識符OID和起始時間tStartTime構(gòu)造成一維關(guān)鍵碼(OID+StartTime)，作為索引目標(biāo)節(jié)點的索引項，借助十六叉樹結(jié)構(gòu)[7]的海量多維數(shù)據(jù)索引能力，對時空區(qū)域內(nèi)目標(biāo)對象的位置進行定位，利用十六叉樹兄弟節(jié)點間的指針關(guān)系進行追根溯源，確定父子節(jié)點與時空坐標(biāo)間的關(guān)系。

2.2 算法流程與存儲設(shè)計

2.2.1STMSR樹的評價指標(biāo)

鑒于多維、多分辨率的時空數(shù)據(jù)索引的綜合考慮，在空間對象上采用MBR劃分為規(guī)則塊，在時間粒度上采用文獻[21-22]的思路，本文提出評價指標(biāo)的數(shù)學(xué)表達式如下：

(1)

式中：Si表示節(jié)點空間坐標(biāo)區(qū)間；R表示多分辨率坐標(biāo)軸；T表示時間坐標(biāo)軸區(qū)間。

選擇該評價指標(biāo)是以三維柯西值不等式為依據(jù)：

(2)

2.2.24DHMSR樹生成算法

STMSR樹型結(jié)構(gòu)可對多種數(shù)據(jù)類型進行查詢，但是每個目標(biāo)節(jié)點數(shù)據(jù)都要經(jīng)過節(jié)點選擇和節(jié)點分裂等復(fù)雜的操作才能插入到索引結(jié)構(gòu)中，這在TGIS中實現(xiàn)動態(tài)數(shù)據(jù)索引較為困難。因此采用一種動態(tài)方式構(gòu)建時空4DHMSR樹索引結(jié)構(gòu)，并給出索引創(chuàng)建算法、插入與分裂算法的描述和算法流程，如圖5、圖6所示。

圖5 4DHMSR樹的創(chuàng)建流程

圖6 選擇節(jié)點的子算法流程

4DHMSR樹的索引創(chuàng)建算法是給STMSR樹設(shè)定扇出(fanout)參數(shù)，即每個目標(biāo)節(jié)點數(shù)據(jù)允許包含最大元組數(shù)目和最小元組數(shù)目，十六叉樹結(jié)構(gòu)的分裂過程中，滿足扇出參數(shù)條件的子節(jié)點將重新計算時空變化范圍，以葉子節(jié)點形式插入到STMSR樹結(jié)構(gòu)中。目標(biāo)節(jié)點數(shù)目小于扇出參數(shù)最小值的子節(jié)點輸出至數(shù)組，將滿足扇出參數(shù)的葉子節(jié)點按序逐一插入到STMSR樹，該過程中不會對數(shù)組中的點重新排序，因為這些時空變化的點幾乎相鄰。而將不滿足扇出參數(shù)的葉子節(jié)點加載到全局節(jié)點數(shù)組中，當(dāng)十六叉樹結(jié)構(gòu)分裂結(jié)束時，即可確定目標(biāo)對象的時空位置，然后采用單點插入的形式將目標(biāo)對象對應(yīng)的節(jié)點逐個插入到STMSR樹形結(jié)構(gòu)。

算法14DHMSR樹的時空索引創(chuàng)建算法。

算法輸入：目標(biāo)屬性數(shù)據(jù)元組集合，STMSR樹扇出參數(shù)為[imin,imax]。

算法輸出：4DHMSR樹的索引結(jié)構(gòu)。

步驟1計算給定時間坐標(biāo)軸區(qū)間T內(nèi)包含所有目標(biāo)屬性數(shù)據(jù)集的最小包圍盒{min(X,Y,Z,T),max(X,Y,Z,T)}并以min(X,Y,Z,T)作為時空對象的起算點，全部點集均是根節(jié)點node中的元組，并創(chuàng)建兩個節(jié)點數(shù)組Array1和Array2。

步驟2如果元組數(shù)目大于imax，則將給定時間區(qū)間內(nèi)的空間均勻劃分八個二級子立方體，每個子立方體中包含8個孩子節(jié)點Childi(i=0,1,2,…,7),并將目標(biāo)節(jié)點分配至對應(yīng)的分支節(jié)點上，進入步驟3；如果根節(jié)點node中元組數(shù)目小于等于imax，則停止分裂。

步驟3清空Array1，逐個遍歷子節(jié)點Childi，如果Childi中的節(jié)點數(shù)目小于imin，將其中的點加入到Array1中，并令A(yù)rray1中的節(jié)點數(shù)目為iStNum，進入步驟4。

步驟5逐個遍歷子立方體中的孩子節(jié)點Childi，如果Childi節(jié)點數(shù)目大于imax，則令根節(jié)點node為Childi，進入步驟2。

步驟6廣度遍歷孩子節(jié)點Childi，如果Childi介于[imin,imax]，則將所有孩子節(jié)點逐個插入到STMSR樹的葉子節(jié)點。

步驟7所有四維十六叉樹結(jié)構(gòu)分裂結(jié)束后，將Array2中的目標(biāo)節(jié)點以元組形式逐個插入到STMSR樹。

步驟8索引構(gòu)建結(jié)束。

算法24DHMSR樹的動態(tài)插入和分裂算法

算法輸入：準(zhǔn)備插入4DHMSR樹中的目標(biāo)節(jié)點數(shù)據(jù)集，已經(jīng)建立的4DHMSR樹索引結(jié)構(gòu)，將要索引目標(biāo)節(jié)點標(biāo)識的索引結(jié)束時間閾值Toendt，清除緩存內(nèi)已訪問節(jié)點的時間閾值Tcnode。

算法輸出：更新后的數(shù)據(jù)索引結(jié)構(gòu)。

步驟1根據(jù)目標(biāo)節(jié)點存儲數(shù)組Array2中的訪問對象，將該對象標(biāo)識符OID作為訪問關(guān)鍵碼，查找對應(yīng)的目標(biāo)節(jié)點數(shù)據(jù)，相對于找到目標(biāo)節(jié)點的結(jié)束時間tEndTime，如果查找目標(biāo)節(jié)點所經(jīng)歷的時間區(qū)間time超出了時間閾值T，進入步驟(2)；否則，將目標(biāo)節(jié)點數(shù)據(jù)集插入到STMSR樹中，并更新數(shù)組Array1，如果數(shù)組Array1已滿，進入步驟2，否則，進入步驟6。

步驟2利用選擇節(jié)點的子算法流程(如圖6所示)，為待訪問節(jié)點node確定插入STMSR樹的父節(jié)點Father，插入node后，如果導(dǎo)致節(jié)點大于imax，則采用節(jié)點分裂子算法將node節(jié)點分為二級子立方體，如果導(dǎo)致該節(jié)點node對應(yīng)的父節(jié)點大于imax，則采用節(jié)點分裂遞歸算法處理，否則，將節(jié)點轉(zhuǎn)入Array2數(shù)組中，如果數(shù)組中的節(jié)點數(shù)目iStNum小于imin，則將Array1中的節(jié)點逐個插入到數(shù)組Array2中，直至數(shù)組Array1中的節(jié)點全部轉(zhuǎn)出。

步驟3將訪問的目標(biāo)對象節(jié)點OID和節(jié)點開始訪問時間tStartTime的組合為一個關(guān)鍵碼添加到十六叉樹存儲結(jié)構(gòu)中，形成新型的數(shù)據(jù)索引項。

步驟4對于生成的新節(jié)點，將其待插入目標(biāo)節(jié)點插入到STMR樹結(jié)構(gòu)中，并由其節(jié)點代替Array1數(shù)組中OID對應(yīng)的node節(jié)點。

步驟5將主緩沖區(qū)中存儲的STMSR樹的節(jié)點數(shù)目Nodesnum進行讀取，當(dāng)節(jié)點數(shù)據(jù)Nodesnum大于給定閾值，則對緩沖區(qū)中未訪問節(jié)點從根節(jié)點開始清除。

步驟6算法終止。

2.2.34DHMSR樹索引存儲設(shè)計

多維、多分辨率和多尺度表達的海量時空數(shù)據(jù)呈指數(shù)級增加，使得時變數(shù)據(jù)管理方法需要大數(shù)據(jù)與云存儲技術(shù)實現(xiàn)[23-25]。由此，對于獨立存儲在數(shù)據(jù)集中的4DHMSR樹索引結(jié)構(gòu)而言，可通過時空索引數(shù)據(jù)集的名稱可對不同的索引信息進行辨識。對于實現(xiàn)多維、多分辨率和多尺度的索引的4DHMSR樹而言，其索引元至少要包括數(shù)據(jù)庫、數(shù)據(jù)集、索引數(shù)據(jù)集、時空維度、分辨率維度、扇出參數(shù)、葉子節(jié)點數(shù)目及根節(jié)點指針編號等目標(biāo)對象標(biāo)識名稱。4DHMSR樹形結(jié)構(gòu)中的根節(jié)點指針編號是訪問存儲文檔的唯一標(biāo)識，通過根節(jié)點指針的編號從數(shù)據(jù)庫中讀取根節(jié)點存儲數(shù)據(jù)[2,20]，進而可對4DHMSR樹中的任意節(jié)點數(shù)據(jù)進行遍歷。為了便于查找時空索引的元數(shù)據(jù)，除了索引的元數(shù)據(jù)外，4DHMSR樹中的非根節(jié)點也被作為文檔存儲在數(shù)據(jù)集中。為了提升存儲空間的利用效率，本文將4DHMSR樹形結(jié)構(gòu)中的子節(jié)點數(shù)據(jù)與元組信息集進行壓縮，用一種十六進制塊Hexademical data類型的數(shù)據(jù)形式存儲文檔，從而減少數(shù)據(jù)存儲位數(shù)和空間，在實際存儲時，通過進制轉(zhuǎn)換實現(xiàn)存儲需要。同時，將目標(biāo)對象標(biāo)識與目標(biāo)節(jié)點數(shù)據(jù)集記錄在葉子節(jié)點中，而將子節(jié)點的時空范圍記錄在非葉子節(jié)點中，從而通過從父節(jié)點遍歷樹結(jié)構(gòu)便可得知子節(jié)點的查詢索引要求是否滿足。

3 工程應(yīng)用與結(jié)果分析

3.1 實驗環(huán)境與數(shù)據(jù)來源

為了驗證4DHMSR樹的索引性能，以某大型露天礦部分采場區(qū)域內(nèi)不同比例尺的運輸?shù)缆窋?shù)據(jù)為例，采用Visual C++ 2010實現(xiàn)了本文的4DHMSR樹生成算法，算法運行環(huán)境為64位的Windows 7和MongoDB數(shù)據(jù)庫，Intel core I5- 760m 3.0 GHz CPU，16 GB主存和500 GB外存。以下實驗數(shù)據(jù)頁面大小設(shè)置為3 KB，十六叉樹結(jié)構(gòu)的最大分裂參數(shù)為100，時空R樹的扇出參數(shù)為40和100，時間屬性則是根據(jù)采場的開采進度計劃時間來進行賦值，數(shù)據(jù)類型為64位整數(shù)類型。使用Brinkhoff時空數(shù)據(jù)生成器形成相同時空對象數(shù)目，從而產(chǎn)生不同尺度下的數(shù)據(jù)集[26]，如表1所示。通過比較比例尺為1 ∶200 000至1 ∶400 000的多維、多分辨率時空數(shù)據(jù)的顯示結(jié)果發(fā)現(xiàn)，它們具有相同的時間點數(shù)目為1 000，空間區(qū)域值{xmin,xmax,ymin,ymax,zmin,zmax}={281,3 935,23 854,30 851,32 516,36 193}。

表1 實驗樣本數(shù)據(jù)集

3.2 時空索引創(chuàng)建性能與耗費指標(biāo)分析

表2 索引耗費時空復(fù)雜性比較

從表2中可知，因為樹中節(jié)點可以記錄綜合結(jié)果，采用4DHMSR樹對相同比例尺下的時空數(shù)據(jù)經(jīng)過多次的索引后，下一次索引查詢的時間明顯低于上一次的查詢時間。另外在進行更低的多分辨率查詢時，上一次多分辨率的綜合結(jié)果能夠被重復(fù)利用，因此如果按照多分辨的高低方向?qū)崿F(xiàn)可視化，可視化時間明顯減少。從表2中同一比例尺下對比三種索引方法的時空性能發(fā)現(xiàn)，在處理時空復(fù)雜性上明顯優(yōu)于另外兩種索引方法。

3.3 結(jié)果對比分析

針對某露天礦采場區(qū)域的開采變化過程，對比例尺為1 ∶200 000至1 ∶400 000的運輸?shù)缆返亩嗑S、多分辨率時空數(shù)據(jù)顯示結(jié)果進行實驗比較，如圖7所示。該實驗過程中的數(shù)據(jù)是以該露天礦采場不同尺度的運輸?shù)缆返貓D為基礎(chǔ)，通過使用Brinkhoff時空數(shù)據(jù)生成器生成相同對象(道路網(wǎng))數(shù)目，形成不同尺度下的數(shù)據(jù)集，然后使用4DHMSR樹的索引創(chuàng)建算法和節(jié)點選擇子算法等對不同尺度數(shù)據(jù)集中的海量路網(wǎng)數(shù)據(jù)進行組織和管理，最后將相同時間點內(nèi)的不同運輸?shù)缆穼ο髷?shù)據(jù)進行索引和查詢，采用可視化工具對索引到的有效數(shù)據(jù)進行區(qū)域建模。

(a) 1 ∶200 000顯示結(jié)果

(b) 1 ∶250 000顯示結(jié)果

(c) 1 ∶300 000顯示結(jié)果

(d) 1 ∶400 000顯示結(jié)果圖7 4DHMSR樹的多維、多分辨率顯示結(jié)果

從圖7的顯示效果可知，特別是圈定的運輸?shù)缆凡糠謪^(qū)域，可以清晰地發(fā)現(xiàn)，由于受到部分采場圖形區(qū)域分辨率的制約，圖7(a)與圖7(b)的比例尺變化程度相對較小，但圖7(a)中部分道路區(qū)域的顯示分辨率要遠(yuǎn)遠(yuǎn)高于圖7(b)，從圖7(c)到圖7(d)的漸變過程發(fā)生明顯變化，這些隨比例尺變化過程是多維、多分辨率時空數(shù)據(jù)表達過程，充分可以證明4DHMSR樹完全支持時空數(shù)據(jù)的多維、多分辨率表達方法。

為了進一步驗證本文索引方法與文獻[24]研究結(jié)果的差異性，將4DMHSR樹與Octree從存儲空間與計算時間兩個方面分別進行了對比，如圖8-圖9所示。兩者的主要區(qū)別是：(1) 4DHMSR樹的索引方法是以4D十六叉樹存儲結(jié)構(gòu)為基礎(chǔ)，4DHMSR樹中的節(jié)點分裂過程中產(chǎn)生的時間復(fù)雜度為O(N)，而MSR樹與Octree樹的時間復(fù)雜度為O(N2)。(2) 4DHMSR樹能夠充分表達多分辨率和多尺度的時空數(shù)據(jù)；而文獻[25]索引方法只是建立在傳統(tǒng)的R樹基礎(chǔ)上，只能表達單分辨率的空間數(shù)據(jù)。(3) 4DHMSR樹的內(nèi)外存儲子索引分別是4D十六叉樹和MSR樹，從而可以較好地索引時空數(shù)據(jù)，無需額外的時間存儲開銷；而文獻[25]提出的索引樹結(jié)構(gòu)的內(nèi)外存子索引結(jié)構(gòu)分別采用Hash表和R樹、B樹，在索引時空數(shù)據(jù)時，特別是時間屬性的表達時，需要額外的內(nèi)外存開銷。

圖8 計算時間的比較

圖9 占用的存儲空間

從圖8可知，隨著地理空間對象尺度的增加，三維八叉樹索引的計算時間明顯增加，但4DHMSR樹索引的計算時間趨于平穩(wěn)狀態(tài)，這表明4DHMSR樹結(jié)構(gòu)憑借十六叉樹結(jié)構(gòu)的時空對象分裂和位置定位，可快速索引到目標(biāo)對象在樹形結(jié)構(gòu)中的位置，從而減少了目標(biāo)對象的索引計算時間。

從圖9可知，隨著地理空間尺度和計算時間的增加，三維八叉樹結(jié)構(gòu)占用的存儲空間要比4DHMSR樹所占用的存儲空間少，這是因為四維十六叉樹結(jié)構(gòu)在給定的分辨率或閾值下，需要對索引的目標(biāo)對象所在的區(qū)域進行遞歸分裂為不同的子立方體，而這個分裂過程需要占用大量的外存和緩存空間，由此導(dǎo)致4DHMSR樹結(jié)構(gòu)占用較多的存儲空間，這需要構(gòu)建符合多維、多分辨率和多尺度時空數(shù)據(jù)索引的刪除和更新算法，實現(xiàn)索引過程中新舊對象的實時清理和更新。

4 結(jié) 語

雖然目前國內(nèi)外對R樹、改進的R樹數(shù)據(jù)結(jié)構(gòu)的研究成果較為豐富，但主要是以空間對象數(shù)據(jù)檢索和八叉樹數(shù)據(jù)結(jié)構(gòu)為主，但在十六叉樹結(jié)構(gòu)與多尺度表達的R樹集成方法中增加時間維度和多分辨率維度，可彌補消耗時間長的不足。由于十六叉樹數(shù)據(jù)結(jié)構(gòu)在表達四維時空對象占用的空間相對較大，但在處理速度上卻比八叉樹結(jié)構(gòu)要快。同時，為了快速創(chuàng)建索引結(jié)構(gòu)和選擇有效的目標(biāo)節(jié)點，設(shè)計了4DHMSR樹的動態(tài)插入和分裂算法，加速索引目標(biāo)數(shù)據(jù)的選擇和插入操作。

本文從理論上對十六叉樹與多尺度表達R樹集成的數(shù)據(jù)結(jié)構(gòu)(4DHMSR樹)進行了探討，將具體的工程實例在計算機上進行了實驗和分析，包括4DHMSR樹的時空性能和可視化，使得十六叉樹與R樹理論探索與實際應(yīng)用向前邁進一步。為了進一步提升十六叉樹結(jié)構(gòu)的性能，設(shè)計出符合4DHMSR樹的記錄更新和刪除算法將是本文下一步研究的方向。