馬 龍 姜 嵐 張正義 程慶榮

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

0 引 言

隨著時(shí)態(tài)地理信息系統(tǒng)(Time Geographic Information System,TGIS)在現(xiàn)代智能交通、車輛軌跡監(jiān)測(cè)和圖像處理等諸多領(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í)空數(shù)據(jù)索引需求，支持多維、多分辨率及多尺度時(shí)空數(shù)據(jù)存儲(chǔ)表達(dá)與索引問題成為當(dāng)前地理信息科學(xué)研究領(lǐng)域普遍關(guān)注的焦點(diǎn)[1-3]。

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

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

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

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

(b) 十六叉樹體元?jiǎng)澐謭D解圖1 十六叉樹結(jié)構(gòu)示意圖

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

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

十六叉樹的搜索原理：每棵十六叉樹是由父節(jié)點(diǎn)和孩子節(jié)點(diǎn)構(gòu)成，每個(gè)父節(jié)點(diǎn)涵蓋16個(gè)子節(jié)點(diǎn)，葉子節(jié)點(diǎn)對(duì)應(yīng)查找表項(xià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í)體對(duì)象的重要度因子[19]將實(shí)體對(duì)象進(jìn)行等級(jí)劃分，并將分辨率較低的視圖對(duì)象數(shù)據(jù)刪除，且在對(duì)象表達(dá)過程中引入顯示分辨率維，利用MSR樹的深度遍歷層次的樹型來表達(dá)多尺度空間數(shù)據(jù)的變化分辨率；其次使用MSR樹的上層樹形結(jié)構(gòu)來表達(dá)空間實(shí)體對(duì)象；最后為了使實(shí)際地理空間特征與所表達(dá)的樹形分支結(jié)果相符合，需考慮地理空間對(duì)象間的關(guān)聯(lián)性，這樣采用綜合算法來實(shí)現(xiàn)多尺度空間數(shù)據(jù)索引問題[20]。

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

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

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

2 4DHMSR樹

2.1 算法思路和多尺度表達(dá)的時(shí)空索引方法

根據(jù)上述MSR樹本身存在的問題可知，索引方法通常受到創(chuàng)建效率、存儲(chǔ)空間、索引時(shí)間等多種指標(biāo)的影響[10]。為了滿足時(shí)空對(duì)象增量數(shù)據(jù)索引的要求，采用4DHMSR樹構(gòu)建時(shí)空數(shù)據(jù)多尺度索引和查詢方法。4DHMSR樹數(shù)據(jù)結(jié)構(gòu)采用嵌套的二級(jí)索引組織形式，其中MR樹為一級(jí)索引結(jié)構(gòu)，四維十六叉樹為二級(jí)數(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樹的基本原理：將空間對(duì)象按照空間認(rèn)知的方法劃分為n個(gè)不同分辨率的子視圖V1,V2,…,Vn，則構(gòu)成圖3所示的時(shí)空數(shù)據(jù)多尺度索引的坐標(biāo)軸，其中V1,V2,…,Vn分別用分辨率軸上的一個(gè)坐標(biāo)點(diǎn)進(jìn)行刻畫，坐標(biāo)點(diǎn)的位置由具有Vi分辨率時(shí)空對(duì)象的最深層次節(jié)點(diǎn)確定。當(dāng)時(shí)空對(duì)象的現(xiàn)時(shí)分辨率介于{Vi,Vj}時(shí)，則Vi,Vj之間某一節(jié)點(diǎn)單元可直接指向時(shí)空目標(biāo)對(duì)象，當(dāng)要查詢某目標(biāo)區(qū)域S內(nèi)分辨率為Vj的子視圖時(shí)，只需對(duì)存儲(chǔ)在十六叉樹中小于等于Vj分辨率的空間對(duì)象和Vj+1的綜合索引結(jié)果進(jìn)行直接查詢；其次對(duì)子MSR樹的搜索對(duì)象和時(shí)空對(duì)象節(jié)點(diǎn)的位置以及Vj深度子樹的查詢進(jìn)行索引。其具體的索引流程如圖4所示。

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

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

2.2 算法流程與存儲(chǔ)設(shè)計(jì)

2.2.1STMSR樹的評(píng)價(jià)指標(biāo)

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

(1)

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

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

(2)

2.2.24DHMSR樹生成算法

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

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

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

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

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

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

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

步驟1計(jì)算給定時(shí)間坐標(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)作為時(shí)空對(duì)象的起算點(diǎn)，全部點(diǎn)集均是根節(jié)點(diǎn)node中的元組，并創(chuàng)建兩個(gè)節(jié)點(diǎn)數(shù)組Array1和Array2。

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

步驟3清空Array1，逐個(gè)遍歷子節(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逐個(gè)遍歷子立方體中的孩子節(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)逐個(gè)插入到STMSR樹的葉子節(jié)點(diǎn)。

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

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

算法24DHMSR樹的動(dòng)態(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)識(shí)的索引結(jié)束時(shí)間閾值Toendt，清除緩存內(nèi)已訪問節(jié)點(diǎn)的時(shí)間閾值Tcnode。

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

步驟1根據(jù)目標(biāo)節(jié)點(diǎn)存儲(chǔ)數(shù)組Array2中的訪問對(duì)象，將該對(duì)象標(biāo)識(shí)符OID作為訪問關(guān)鍵碼，查找對(duì)應(yīng)的目標(biāo)節(jié)點(diǎn)數(shù)據(jù)，相對(duì)于找到目標(biāo)節(jié)點(diǎn)的結(jié)束時(shí)間tEndTime，如果查找目標(biāo)節(jié)點(diǎn)所經(jīng)歷的時(shí)間區(qū)間time超出了時(shí)間閾值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)分為二級(jí)子立方體，如果導(dǎo)致該節(jié)點(diǎn)node對(duì)應(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)逐個(gè)插入到數(shù)組Array2中，直至數(shù)組Array1中的節(jié)點(diǎn)全部轉(zhuǎn)出。

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

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

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

步驟6算法終止。

2.2.34DHMSR樹索引存儲(chǔ)設(shè)計(jì)

多維、多分辨率和多尺度表達(dá)的海量時(shí)空數(shù)據(jù)呈指數(shù)級(jí)增加，使得時(shí)變數(shù)據(jù)管理方法需要大數(shù)據(jù)與云存儲(chǔ)技術(shù)實(shí)現(xiàn)[23-25]。由此，對(duì)于獨(dú)立存儲(chǔ)在數(shù)據(jù)集中的4DHMSR樹索引結(jié)構(gòu)而言，可通過時(shí)空索引數(shù)據(jù)集的名稱可對(duì)不同的索引信息進(jìn)行辨識(shí)。對(duì)于實(shí)現(xiàn)多維、多分辨率和多尺度的索引的4DHMSR樹而言，其索引元至少要包括數(shù)據(jù)庫、數(shù)據(jù)集、索引數(shù)據(jù)集、時(shí)空維度、分辨率維度、扇出參數(shù)、葉子節(jié)點(diǎn)數(shù)目及根節(jié)點(diǎn)指針編號(hào)等目標(biāo)對(duì)象標(biāo)識(shí)名稱。4DHMSR樹形結(jié)構(gòu)中的根節(jié)點(diǎn)指針編號(hào)是訪問存儲(chǔ)文檔的唯一標(biāo)識(shí)，通過根節(jié)點(diǎn)指針的編號(hào)從數(shù)據(jù)庫中讀取根節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)[2,20]，進(jìn)而可對(duì)4DHMSR樹中的任意節(jié)點(diǎn)數(shù)據(jù)進(jìn)行遍歷。為了便于查找時(shí)空索引的元數(shù)據(jù)，除了索引的元數(shù)據(jù)外，4DHMSR樹中的非根節(jié)點(diǎn)也被作為文檔存儲(chǔ)在數(shù)據(jù)集中。為了提升存儲(chǔ)空間的利用效率，本文將4DHMSR樹形結(jié)構(gòu)中的子節(jié)點(diǎn)數(shù)據(jù)與元組信息集進(jìn)行壓縮，用一種十六進(jìn)制塊Hexademical data類型的數(shù)據(jù)形式存儲(chǔ)文檔，從而減少數(shù)據(jù)存儲(chǔ)位數(shù)和空間，在實(shí)際存儲(chǔ)時(shí)，通過進(jìn)制轉(zhuǎn)換實(shí)現(xiàn)存儲(chǔ)需要。同時(shí)，將目標(biāo)對(duì)象標(biāo)識(shí)與目標(biāo)節(jié)點(diǎn)數(shù)據(jù)集記錄在葉子節(jié)點(diǎn)中，而將子節(jié)點(diǎn)的時(shí)空范圍記錄在非葉子節(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樹的索引性能，以某大型露天礦部分采場(chǎng)區(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，時(shí)空R樹的扇出參數(shù)為40和100，時(shí)間屬性則是根據(jù)采場(chǎng)的開采進(jìn)度計(jì)劃時(shí)間來進(jìn)行賦值，數(shù)據(jù)類型為64位整數(shù)類型。使用Brinkhoff時(shí)空數(shù)據(jù)生成器形成相同時(shí)空對(duì)象數(shù)目，從而產(chǎn)生不同尺度下的數(shù)據(jù)集[26]，如表1所示。通過比較比例尺為1 ∶200 000至1 ∶400 000的多維、多分辨率時(shí)空數(shù)據(jù)的顯示結(jié)果發(fā)現(xiàn)，它們具有相同的時(shí)間點(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 時(shí)空索引創(chuàng)建性能與耗費(fèi)指標(biāo)分析

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

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

3.3 結(jié)果對(duì)比分析

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

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

圖8 計(jì)算時(shí)間的比較

圖9 占用的存儲(chǔ)空間

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

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

4 結(jié) 語

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

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