馬 龍 姜 嵐 張正義 程慶榮

1(西安航空學(xué)院經(jīng)濟(jì)管理學(xué)院 陜西 西安 710077) 2(西安航空學(xué)院計算機(jī)學(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ù)表達(dá)形式多樣化，用戶訪問數(shù)據(jù)量大。然而，為了解決多用戶視角下TGIS時空數(shù)據(jù)索引需求，支持多維、多分辨率及多尺度時空數(shù)據(jù)存儲表達(dá)與索引問題成為當(dāng)前地理信息科學(xué)研究領(lǐng)域普遍關(guān)注的焦點(diǎn)[1-3]。

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

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

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

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

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

十六叉的體元劃分原理與八叉樹的對象劃分原理基本類似，只是八叉樹用于表達(dá)三維空間目標(biāo)，而十六叉樹用于表達(dá)四維時空目，且所有構(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é)點(diǎn)，它們屬于同一個層次，且達(dá)到所需的分辨率要求。分解的結(jié)果類似一棵倒立的層次樹，樹的內(nèi)部節(jié)點(diǎn)上涵蓋十六個孩子節(jié)點(diǎn)[7]。

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

1.2 多尺度表達(dá)的R樹

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

根據(jù)圖2(a)中MSR樹的矩形分塊可以看出，在樹形分支R12中的空間對象要素A與樹形分支R16中的空間對象要素B均屬于樹形分支R6。首先，根據(jù)MSR樹的基本思想，為了使實(shí)際地理空間特征與所表達(dá)的樹形分支結(jié)果相符合，需考慮到地理空間對象要素之間的關(guān)聯(lián)關(guān)系、要素與周圍環(huán)境的語義關(guān)系，這樣可使用綜合算法將空間對象要素A和B進(jìn)行合并操作。然后，利用空間對象要素的分裂算法，將樹形分支R6進(jìn)行分裂成孩子節(jié)點(diǎn)，并利用插入算法將樹形分支R12插入R6分支節(jié)點(diǎn)內(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 算法思路和多尺度表達(dá)的時空索引方法

根據(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)點(diǎn)進(jìn)行刻畫，坐標(biāo)點(diǎn)的位置由具有Vi分辨率時空對象的最深層次節(jié)點(diǎn)確定。當(dāng)時空對象的現(xiàn)時分辨率介于{Vi,Vj}時，則Vi,Vj之間某一節(jié)點(diǎn)單元可直接指向時空目標(biāo)對象，當(dāng)要查詢某目標(biāo)區(qū)域S內(nèi)分辨率為Vj的子視圖時，只需對存儲在十六叉樹中小于等于Vj分辨率的空間對象和Vj+1的綜合索引結(jié)果進(jìn)行直接查詢；其次對子MSR樹的搜索對象和時空對象節(jié)點(diǎn)的位置以及Vj深度子樹的查詢進(jìn)行索引。其具體的索引流程如圖4所示。

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

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

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

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

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

(1)

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

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

(2)

2.2.24DHMSR樹生成算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟6算法終止。

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

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

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

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

為了驗(yàn)證4DHMSR樹的索引性能，以某大型露天礦部分采場區(qū)域內(nèi)不同比例尺的運(yùn)輸?shù)缆窋?shù)據(jù)為例，采用Visual C++ 2010實(shí)現(xiàn)了本文的4DHMSR樹生成算法，算法運(yùn)行環(huán)境為64位的Windows 7和MongoDB數(shù)據(jù)庫，Intel core I5- 760m 3.0 GHz CPU，16 GB主存和500 GB外存。以下實(shí)驗(yàn)數(shù)據(jù)頁面大小設(shè)置為3 KB，十六叉樹結(jié)構(gòu)的最大分裂參數(shù)為100，時空R樹的扇出參數(shù)為40和100，時間屬性則是根據(jù)采場的開采進(jìn)度計劃時間來進(jìn)行賦值，數(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)，它們具有相同的時間點(diǎn)數(shù)目為1 000，空間區(qū)域值{xmin,xmax,ymin,ymax,zmin,zmax}={281,3 935,23 854,30 851,32 516,36 193}。

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

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

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

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

3.3 結(jié)果對比分析

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

為了進(jìn)一步驗(yàn)證本文索引方法與文獻(xiàn)[24]研究結(jié)果的差異性，將4DMHSR樹與Octree從存儲空間與計算時間兩個方面分別進(jìn)行了對比，如圖8-圖9所示。兩者的主要區(qū)別是：(1) 4DHMSR樹的索引方法是以4D十六叉樹存儲結(jié)構(gòu)為基礎(chǔ)，4DHMSR樹中的節(jié)點(diǎn)分裂過程中產(chǎn)生的時間復(fù)雜度為O(N)，而MSR樹與Octree樹的時間復(fù)雜度為O(N2)。(2) 4DHMSR樹能夠充分表達(dá)多分辨率和多尺度的時空數(shù)據(jù)；而文獻(xiàn)[25]索引方法只是建立在傳統(tǒng)的R樹基礎(chǔ)上，只能表達(dá)單分辨率的空間數(shù)據(jù)。(3) 4DHMSR樹的內(nèi)外存儲子索引分別是4D十六叉樹和MSR樹，從而可以較好地索引時空數(shù)據(jù)，無需額外的時間存儲開銷；而文獻(xiàn)[25]提出的索引樹結(jié)構(gòu)的內(nèi)外存子索引結(jié)構(gòu)分別采用Hash表和R樹、B樹，在索引時空數(shù)據(jù)時，特別是時間屬性的表達(dá)時，需要額外的內(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樹所占用的存儲空間少，這是因?yàn)樗木S十六叉樹結(jié)構(gòu)在給定的分辨率或閾值下，需要對索引的目標(biāo)對象所在的區(qū)域進(jìn)行遞歸分裂為不同的子立方體，而這個分裂過程需要占用大量的外存和緩存空間，由此導(dǎo)致4DHMSR樹結(jié)構(gòu)占用較多的存儲空間，這需要構(gòu)建符合多維、多分辨率和多尺度時空數(shù)據(jù)索引的刪除和更新算法，實(shí)現(xiàn)索引過程中新舊對象的實(shí)時清理和更新。

4 結(jié) 語

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

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