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

馬 龍 姜 嵐 張正義 程慶榮

1(西安航空學院經濟管理學院 陜西 西安 710077) 2(西安航空學院計算機學院 陜西 西安 710077)

0 引 言

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

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

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

1 時空數據索引結構分析

1.1 十六叉樹結構

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

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

(b) 十六叉樹體元劃分圖解圖1 十六叉樹結構示意圖

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

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

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

1.2 多尺度表達的R樹

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

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

(a) MSR樹矩形分塊結果

(b) MSR樹結構圖2 MSR樹的基本結構[19]

2 4DHMSR樹

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

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

圖3 4DHMSR樹數據結構的組織結構[19]

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

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

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

2.2 算法流程與存儲設計

2.2.1STMSR樹的評價指標

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

(1)

式中：Si表示節點空間坐標區間；R表示多分辨率坐標軸；T表示時間坐標軸區間。

選擇該評價指標是以三維柯西值不等式為依據：

(2)

2.2.24DHMSR樹生成算法

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

圖5 4DHMSR樹的創建流程

圖6 選擇節點的子算法流程

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

算法14DHMSR樹的時空索引創建算法。

算法輸入：目標屬性數據元組集合，STMSR樹扇出參數為[imin,imax]。

算法輸出：4DHMSR樹的索引結構。

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

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

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

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

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

步驟7所有四維十六叉樹結構分裂結束后，將Array2中的目標節點以元組形式逐個插入到STMSR樹。

步驟8索引構建結束。

算法24DHMSR樹的動態插入和分裂算法

算法輸入：準備插入4DHMSR樹中的目標節點數據集，已經建立的4DHMSR樹索引結構，將要索引目標節點標識的索引結束時間閾值Toendt，清除緩存內已訪問節點的時間閾值Tcnode。

算法輸出：更新后的數據索引結構。

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

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

步驟3將訪問的目標對象節點OID和節點開始訪問時間tStartTime的組合為一個關鍵碼添加到十六叉樹存儲結構中，形成新型的數據索引項。

步驟4對于生成的新節點，將其待插入目標節點插入到STMR樹結構中，并由其節點代替Array1數組中OID對應的node節點。

步驟5將主緩沖區中存儲的STMSR樹的節點數目Nodesnum進行讀取，當節點數據Nodesnum大于給定閾值，則對緩沖區中未訪問節點從根節點開始清除。

步驟6算法終止。

2.2.34DHMSR樹索引存儲設計

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

3 工程應用與結果分析

3.1 實驗環境與數據來源

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

表1 實驗樣本數據集

3.2 時空索引創建性能與耗費指標分析

表2 索引耗費時空復雜性比較

從表2中可知，因為樹中節點可以記錄綜合結果，采用4DHMSR樹對相同比例尺下的時空數據經過多次的索引后，下一次索引查詢的時間明顯低于上一次的查詢時間。另外在進行更低的多分辨率查詢時，上一次多分辨率的綜合結果能夠被重復利用，因此如果按照多分辨的高低方向實現可視化，可視化時間明顯減少。從表2中同一比例尺下對比三種索引方法的時空性能發現，在處理時空復雜性上明顯優于另外兩種索引方法。

3.3 結果對比分析

針對某露天礦采場區域的開采變化過程，對比例尺為1 ∶200 000至1 ∶400 000的運輸道路的多維、多分辨率時空數據顯示結果進行實驗比較，如圖7所示。該實驗過程中的數據是以該露天礦采場不同尺度的運輸道路地圖為基礎，通過使用Brinkhoff時空數據生成器生成相同對象(道路網)數目，形成不同尺度下的數據集，然后使用4DHMSR樹的索引創建算法和節點選擇子算法等對不同尺度數據集中的海量路網數據進行組織和管理，最后將相同時間點內的不同運輸道路對象數據進行索引和查詢，采用可視化工具對索引到的有效數據進行區域建模。

(a) 1 ∶200 000顯示結果

(b) 1 ∶250 000顯示結果

(c) 1 ∶300 000顯示結果

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

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

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

圖8 計算時間的比較

圖9 占用的存儲空間

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

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

4 結 語

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

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