郜允兵，高秉博，李曉嵐，潘瑜春，張曉東

（1.中國農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院，北京 100083；2.北京農(nóng)業(yè)信息技術(shù)研究中心，北京 100097；3.國家農(nóng)業(yè)信息化工程技術(shù)研究中心，北京100097；4.農(nóng)業(yè)部農(nóng)業(yè)信息技術(shù)重點實驗室，北京 100097；5.北京市農(nóng)業(yè)物聯(lián)網(wǎng)工程技術(shù)研究中心，北京 100097）

長時間序列土地利用數(shù)據(jù)時空索引技術(shù)研究

郜允兵1，2，3，高秉博2，3，4，李曉嵐2，3，5，潘瑜春2，3，4，張曉東1

（1.中國農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院，北京 100083；2.北京農(nóng)業(yè)信息技術(shù)研究中心，北京 100097；3.國家農(nóng)業(yè)信息化工程技術(shù)研究中心，北京100097；4.農(nóng)業(yè)部農(nóng)業(yè)信息技術(shù)重點實驗室，北京 100097；5.北京市農(nóng)業(yè)物聯(lián)網(wǎng)工程技術(shù)研究中心，北京 100097）

研究目的：研究支持一調(diào)、二調(diào)海量土地利用時空數(shù)據(jù)變化分析及趨勢預(yù)測的高效索引技術(shù)。研究方法：在分析格網(wǎng)索引、HR索引基礎(chǔ)上，針對常用土地利用時空數(shù)據(jù)模型應(yīng)用場景，提出了適于長時間序列土地利用數(shù)據(jù)檢索的混合時空的索引方法。研究結(jié)果：（1）以行政區(qū)邊界來劃分空間格網(wǎng)，在格網(wǎng)基礎(chǔ)上以變更調(diào)查年為時間標尺建立對應(yīng)的HR樹索引，將基態(tài)現(xiàn)狀和變更增量時空對象的索引信息保存為索引結(jié)點，建立了基于格網(wǎng)與HR樹的混合時空索引結(jié)構(gòu)；（2）基于此索引結(jié)構(gòu)，研究并實現(xiàn)了時空混合索引樹生成、索引查詢、索引刪除、索引新增的具體算法。研究結(jié)論：以某縣域土地利用變化分析中的幾種典型情境為例，對比分析了格網(wǎng)索引、HR索引和混合時空索引檢索時間復(fù)雜度，結(jié)果表明該索引方法具有較好的查詢效率，滿足土地利用變化分析數(shù)據(jù)時空查詢的需求。

土地信息；時空數(shù)據(jù)模型；時空索引；格網(wǎng)索引；HR樹；混合索引

1　引言

自1984年開展土地調(diào)查工作以來，中國完成了第一次、第二次全國性土地調(diào)查，開展了年度土地變更調(diào)查工作，積累了海量的土地利用數(shù)據(jù)。隨著城鎮(zhèn)化進程的推進，土地供需矛盾加劇，需對土地利用數(shù)據(jù)進行縱向分析和深入挖掘，探討其變化規(guī)律并預(yù)測變化趨勢，為國土資源政策提供更直觀的支撐信息［1-4］。土地利用變化分析涉及海量時空數(shù)據(jù)查詢，時間跨度大，地域關(guān)聯(lián)強，時間片查詢（歷史回溯、歷史狀態(tài)重建）、時間段查詢（變更流向、地類變化率、用地異常監(jiān)測），以及時空關(guān)聯(lián)查詢（土地利用動態(tài)度、區(qū)域變化熱點分析）往往比較復(fù)雜［5-8］，這對時空數(shù)據(jù)庫查詢效率提出了更高的要求［9-11］。時空索引技術(shù)多是在R樹系列索引［12］、格網(wǎng)索引［13-14］］等空間索引的基礎(chǔ)上演變而來［15-16］。基于R樹的時空索引技術(shù)主要包括HR樹［10-17］、TR樹［18］、MVR樹［19］或3DR樹［20］等時空索引，這些時空索引技術(shù)將地理對象的變化看作多個時間片要素變化與持久對象的時空疊加，或者將時間信息作為檢索的一維加入到R樹中，可同時進行插入、刪除和查詢操作，后期維護成本較低，但作為面向?qū)ο蟮姆指罘椒ǎ?jié)點空間大小不固定，節(jié)點間重疊率高。格網(wǎng)索引［21-23］作為基于Hash散列存儲的索引方法，其基本思想是將研究對象空間劃分成一定大小的網(wǎng)格，記錄每個格網(wǎng)下所對應(yīng)的空間對象。格網(wǎng)索引查詢操作簡單，容易實現(xiàn)，但空間存儲量大且容易出現(xiàn)空間對象重復(fù)存儲的情況?；陂L時間序列的土地利用時空數(shù)據(jù)索引單純使用格網(wǎng)索引，數(shù)據(jù)存儲量大且格網(wǎng)結(jié)構(gòu)可調(diào)節(jié)性差不易于維護，而簡單地使用R樹系列索引往往搜索深度過大，且節(jié)點間的關(guān)系復(fù)雜，檢索效率不高。本文在時空數(shù)據(jù)模型分析的基礎(chǔ)上，提出了基于格網(wǎng)與HR樹結(jié)構(gòu)的混合時空索引模型，設(shè)計了土地利用時空索引結(jié)構(gòu)，采用空間聚類法構(gòu)建索引樹，并對其相關(guān)操作算法進行描述，最后結(jié)合土地利用變化分析典型實例，對比分析了該混合索引與格網(wǎng)索引、HR樹索引的檢索性能。

2　時空數(shù)據(jù)模型

時空索引技術(shù)與時空數(shù)據(jù)模型息息相關(guān)，并不存在一種普遍應(yīng)用于所有需求環(huán)境且高效的索引技術(shù)。目前常用的時空數(shù)據(jù)模型有序列快照模型、基態(tài)修正模型、時空復(fù)合模型、面向?qū)ο髸r空數(shù)據(jù)模型。土地利用數(shù)據(jù)為靜態(tài)結(jié)構(gòu)數(shù)據(jù)，數(shù)據(jù)一旦變化會在較長一段時間內(nèi)處于穩(wěn)定狀態(tài)，用多個時間片上快照數(shù)據(jù)與年度土地利用變化增量數(shù)據(jù)這兩種方式來表達土地利用時空變化比較合適。從土地利用數(shù)據(jù)變化特征來看，采用基態(tài)修正模型易于數(shù)據(jù)管理與軟件實現(xiàn)。

雖然基態(tài)修正模型降低了數(shù)據(jù)冗余，提高了時態(tài)分辨率，但是增加了時空操作的復(fù)雜性，對于時空對象索引、時空關(guān)系表達和時空分析難度較高。為更好描述時空對象間關(guān)系，簡化時空分析過程，降低時空操作復(fù)雜度，在設(shè)計模型時引入了事件機制，通過變更事件記錄變化前后的歷史繼承關(guān)系，通過重建事件記錄一調(diào)、二調(diào)不同歷史時期要素重建前后關(guān)聯(lián)關(guān)系、重建類型［24］（圖1）。在要素實體中記錄要素實體變更前后產(chǎn)生消亡時間。重建某區(qū)域現(xiàn)狀時，則可以基態(tài)數(shù)據(jù)為基準，通過多次疊加修正數(shù)據(jù)獲取某一時點的土地利用狀態(tài)。土地利用要素回溯或者變化流向分析時，則可從某個時點為基準遍歷修正數(shù)據(jù)及繼承關(guān)聯(lián)獲取某時間段內(nèi)要素變化情況。

圖1　基于事件組的多基態(tài)修正時空數(shù)據(jù)模型［24］Fig.1　The multiple base states with amendments data model based on event group

3　混合時空索引設(shè)計

歷史時刻再現(xiàn)、土地利用變化指數(shù)分析［25］、土地利用變化熱點區(qū)域探測、土地利用變化趨勢分析及時空相關(guān)性分析等土地利用業(yè)務(wù)分析往往以當(dāng)前或者某個時點的行政區(qū)劃為基本單位進行查詢、分析，行政區(qū)單元在一定時間范圍內(nèi)具有相對的穩(wěn)定性。因此，在對修正模型中的基態(tài)現(xiàn)狀數(shù)據(jù)和變更增量建立索引時，可以行政區(qū)邊界（縣、鄉(xiāng)、村）作為網(wǎng)格劃分單元進行多層級格網(wǎng)的劃分。將多級行政區(qū)邊界看作時空數(shù)據(jù)桶，本行政區(qū)邊界內(nèi)所有要素對象均存放在該桶內(nèi)，有效避免規(guī)則網(wǎng)格劃分法引起的要素對象跨區(qū)劃分使得要素對象在多個格網(wǎng)存放造成存儲冗余、檢索復(fù)雜等問題。其次，土地利用現(xiàn)狀調(diào)查是以年為周期進行，因此在構(gòu)建時空索引時，按現(xiàn)狀調(diào)查的周期對基本分區(qū)單元在時間維上切割，形成基本分區(qū)時空索引子區(qū)。

對于每個格網(wǎng)時空子區(qū)，采用R樹分裂法建立索引。時空索引結(jié)點記錄某個時間點上變更要素或者現(xiàn)狀要素的空間范圍和要素ID。其中，空間域記錄子結(jié)點包含的要素實體幾何最小外包矩形（MBR）集及其坐落單位代碼（ZLDM）。索引非葉子結(jié)點結(jié)構(gòu)為，葉子結(jié)點結(jié)構(gòu)為。時空混合索引結(jié)構(gòu)如圖2所示。假定以縣域歷年土地利用數(shù)據(jù)為數(shù)據(jù)檢索對象，則年度變更增量和多基態(tài)現(xiàn)狀均可按年度時間片分割，變更增量和多基態(tài)時空索引結(jié)構(gòu)如圖3所示。

時空索引結(jié)構(gòu)中，t1，t2，…，tn為變更增量以及基態(tài)現(xiàn)狀記錄時間。C1，C2，…，Cn代表研究區(qū)內(nèi)按行政區(qū)邊界劃分的近似分區(qū)單元，且M≥Cn≥1。ZLDM1，ZLDM2，…，ZLDMn為坐落代碼，代表MBR對應(yīng)的行政區(qū)域。基本格網(wǎng)按年度變化間隔劃分，形成tn個時空桶，M≥tn≥1。采用C-Liner分裂規(guī)則（空間距離聚類法）對要素對象進行結(jié)點劃分，建立基本格網(wǎng)時空索引。設(shè)O為時空子區(qū)內(nèi)要素總數(shù)最大值，K為Cn基本格網(wǎng)時空桶TR樹劃分的層數(shù)，則結(jié)點Node取值為［m，M］，m≥2，M≤O/k。

4　時空索引樹生成及操作

4.1時空索引樹生成

圖2　多級格網(wǎng)與HR樹混合索引結(jié)構(gòu)Fig.2　The hybrid index structure of multi-level grid and HR-tree

圖3　基于基態(tài)+變更增量的時空索引結(jié)構(gòu)Fig.3　The spatio-temporal index structure based on state and change increment objects

基于以上索引結(jié)構(gòu)設(shè)計，在生成索引樹時，假定多年變更和基態(tài)年的零星地物、線狀地物、地類圖斑分別存放在對應(yīng)的空間數(shù)據(jù)表中，且行政邊界不變，其具體的生成過程如下：Step1：加載行政區(qū)圖層和零星地物（或線狀地物、地類圖斑），獲取整個研究區(qū)域的外邊界最小矩形（MBR）。生成根結(jié)點，記錄根節(jié)點MBR、坐落代碼ZLDM、起始時間t1、當(dāng)前時間t2（t2用Now表示）以及指向子結(jié)點的首地址。Step2： 基于行政區(qū)劃分格網(wǎng)。從研究區(qū)的行政區(qū)圖中，提取行政區(qū)最小外接矩形（MBR），形成一級格網(wǎng)。Step3：遍歷落入一級格網(wǎng)中的地類圖斑，若行政區(qū)為鎮(zhèn)級以上，則進一步細分格網(wǎng)，否則格網(wǎng)劃分結(jié)束。Step4：依次生成格網(wǎng)結(jié)點，記錄結(jié)點MBR、坐落代碼ZLDM、起始時間t1、當(dāng)前時間t2（t2用Now表示）以及指向子結(jié)點的地址。Step5：基于時間段劃分。保持網(wǎng)格空間范圍不變，按土地利用變更頻率，對格網(wǎng)結(jié)點進一步細分，形成年度變更格網(wǎng)。結(jié)點中MBR 為各級行政區(qū)最小外接邊界矩形，ZLDM為該MBR代表的行政區(qū)代碼，結(jié)點時間段為年度變更起止時間。Step6：遍歷所有空間要素，根據(jù)其空間位置和要素變更時間或者要素快照年度，將它劃分到對應(yīng)的格網(wǎng)中。土地利用要素不存在跨格網(wǎng)情況。按年度變更、基態(tài)快照兩個空間數(shù)據(jù)庫分別對零星地物、線狀地物、地類圖斑進行遍歷，允許結(jié)點內(nèi)要素為空。Step7：對于每個非空時空格網(wǎng)結(jié)點，采用R樹動態(tài)分裂法自上而下建立索引。R 樹每個結(jié)點包括的單元個數(shù)介于m 與M 之間，m≥1，M＜50。不允許要素對象出現(xiàn)在非葉結(jié)點。當(dāng)對象的索引項插入到R樹中時，如果R樹結(jié)點存儲的索引項數(shù)量超過最大值時，則結(jié)點將發(fā)生溢出，此時需要進行結(jié)點分裂。

結(jié)點分裂采用分割聚類方法對溢出結(jié)點分裂，零星地物、線狀地物、地類圖斑等在結(jié)點分裂時可用空間對象幾何中心的遠近來衡量待選要素對象與已有要素集的聚集程度。其中，對于零星地物直接采用點集幾何中心表示；對于線狀地物、地類圖斑聚類則采用最小外接矩形的幾何中心近似表示。零星地物、線狀地物、地類圖斑等要素幾何中心主要采用點集幾何中心及矩形幾何中心方法計算［26］，如式2—式3：

點集幾何中心［26］：點集由N個點P1，P2，…，Pn組成，N個點的坐標為Pi（Xi，Yi），i∈（1，2，…，n），則這N個點的幾何中心定義為：

矩形幾何中心［26］：由M個矩形r1，r2，…，rm組成，M個矩形的邊界坐標為ri（min_xi，min_yi，max_xi，max_yi），i∈（1，2，…，m），其中（min_xi，min_yi）為矩形ri的左下角坐標，（max_xi，max_yi）為矩形氣的右上角坐標，設(shè)M個矩形的面積為area（ri），i∈（1，2，…，m），則M個矩形的幾何中心定義為：

以上時空索引樹生成解決了數(shù)據(jù)庫中已有土地利用變更增量數(shù)據(jù)、多基態(tài)現(xiàn)狀數(shù)據(jù)的索引樹的構(gòu)建。但對于新增的年度調(diào)查的增量數(shù)據(jù)和基態(tài)現(xiàn)狀數(shù)據(jù)集批量插入，舊基態(tài)現(xiàn)狀數(shù)據(jù)、變更增量刪除等時空索引的維護，時空查詢過程中區(qū)域時空索引樹快速建立，數(shù)據(jù)批量加載等問題還需進一步討論。

4.2時空索引操作

時空查詢處理主要分為過濾和精煉這兩步查詢求精過程，基于格網(wǎng)以及HR樹的空間查詢算法基本上集中在過濾步驟。時空查詢的基本思路：（1）加載根結(jié)點、行政區(qū)劃結(jié)點以及按時間段劃分結(jié)點，生成時空格網(wǎng)索引樹；（2）按查詢條件遍歷研究區(qū)所有與查詢窗口相交的格網(wǎng)結(jié)點，按時間段逐個判斷時空格網(wǎng)結(jié)點，初步篩選出HR樹結(jié)點，若為空，重新設(shè)置查詢條件；（3）生成查詢式Query（空間區(qū)域，時間段），在HR 樹中遍歷返回候選要素集，加載要素對象幾何、生命周期進一步判斷，最終形成查詢結(jié)構(gòu)。在具體的算法設(shè)計時，點要素和線面要素分別進行查詢。

在土地利用時空數(shù)據(jù)庫運行維護過程中，往往會對基態(tài)現(xiàn)狀、年度變更增量數(shù)據(jù)進行調(diào)整。年度變更調(diào)查增量數(shù)據(jù)入庫后生成當(dāng)前年（T年）的現(xiàn)狀，數(shù)據(jù)庫會對當(dāng)前年的基態(tài)進行調(diào)整，刪除歷史基態(tài)（T-1年），設(shè)置當(dāng)期年現(xiàn)狀為當(dāng)前基態(tài)。可以看出，為了保持時空數(shù)據(jù)維護更新檢索一致性，時空索引應(yīng)能進行動態(tài)批量維護，對無用的索引進行動態(tài)刪除。年度變更增量數(shù)據(jù)、基態(tài)現(xiàn)狀數(shù)據(jù)調(diào)整，可以作為新增數(shù)據(jù)插入和歷史變更數(shù)據(jù)刪除。

對新增要素對象的插入方法為：（1）加載已有索引生成樹，根結(jié)點、行政區(qū)劃結(jié)點以及按時間段劃分結(jié)點；（2）在每個行政區(qū)格網(wǎng)結(jié)點下新增年度變更子結(jié)點，結(jié)點時間段為t∈（T-1，T）；（3）對比行政區(qū)矩形與新增要素對象外接矩形，將每個要素對象存放到新增結(jié)點下；（4）按時空索引樹生成中結(jié)點分裂方法對要素進行組織，構(gòu)建索引樹。零星地物作為點要素，在具體的算法設(shè)計時，分作點要素插入和線面要素插入分別進行。

歷史變更數(shù)據(jù)刪除的具體步驟如下：（1）加載已有索引生成樹，根結(jié)點、行政區(qū)劃結(jié)點以及按時間片劃分結(jié)點；（2）按基態(tài)現(xiàn)狀的時間T或者變更時間T在行政區(qū)格網(wǎng)中遍歷查找對應(yīng)的結(jié)點；（3）若返回子結(jié)點為空則無此索引結(jié)構(gòu)；否則，刪除此結(jié)點以及結(jié)點下所有子結(jié)點。由于零星地物是點要素，在具體的算法設(shè)計時，點要素和線面要素分別進行刪除。

5　應(yīng)用實證分析

以某縣域2005年、2008年以及2009—2013年土地利用調(diào)查地類圖斑、線狀地物、零星地物數(shù)據(jù)為基礎(chǔ)，基于上文提到的多基態(tài)修正數(shù)據(jù)模型，采用Microsoft SQL 2008數(shù)據(jù)庫系統(tǒng)，建立了長時序時空數(shù)據(jù)庫。在數(shù)據(jù)庫中存儲2013年、2008年完整現(xiàn)狀作為基態(tài)，并以2013年作為查詢起點，僅在數(shù)據(jù)庫中存儲2005年、2009—2012年等時點的變更增量、變更關(guān)系（變更事件、時態(tài)拓撲關(guān)系），以及2005年、2008年一調(diào)數(shù)據(jù)一致化轉(zhuǎn)化前后要素轉(zhuǎn)換關(guān)系［24］（具體轉(zhuǎn)換細節(jié)參看其他文獻，不贅述）。在原有土地利用時態(tài)數(shù)據(jù)管理系統(tǒng)基礎(chǔ)上，采用C#語言實現(xiàn)了索引樹生成及索引操作算法，建立了多級格網(wǎng)與HR樹的混合索引，如圖4（a）、（b），圖5（a）所示。以行政區(qū)（鄉(xiāng)鎮(zhèn)和村）為網(wǎng)格劃為單元，建立空間數(shù)據(jù)的二級格網(wǎng)索引，并對各時點基態(tài)及增量數(shù)據(jù)按年度劃分后，分別建立現(xiàn)狀、變更增量HR樹索引結(jié)點，在實體數(shù)據(jù)庫中建立時空索引表結(jié)構(gòu)，記錄多級格網(wǎng)與HR樹相結(jié)合的混合索引樹。

圖4　構(gòu)建多級格網(wǎng)與HR樹的混合索引Fig.4　Build the hybrid index based on multiple-level grid and HR tree

圖5　三種索引方法的結(jié)點分布Fig.5　The nodes distribution of three index methods

土地利用變化分析涉及的時空查詢類型有：簡單時態(tài)查詢、時態(tài)范圍查詢、簡單時空查詢、時空范圍查詢、時空連接查詢、時空對象最近鄰居查詢。其中，簡單時態(tài)查詢是指查找指定時刻要素對象的狀態(tài)，如查詢縣域內(nèi)某圖斑在2013年的土地利用類型及面積；時態(tài)范圍查詢指查詢某一時間段內(nèi)某要素對象發(fā)生的變化，如查詢縣域某圖斑2009—2013年間變化情況（如地類變更及面積變化）；簡單時空查詢指查詢某研究區(qū)域在某時刻的歷史狀態(tài)，如按二級地類統(tǒng)計縣域內(nèi)某鄉(xiāng)鎮(zhèn)在2010年土地利用現(xiàn)狀情況；時空范圍查詢指查詢某時期內(nèi)某區(qū)域時空對象的變化，如統(tǒng)計縣域內(nèi)某鄉(xiāng)鎮(zhèn)2009—2013年耕地轉(zhuǎn)移為其他地類的情況；時空連接查詢指給定兩個時空關(guān)系，找出這兩個關(guān)系中在指定時間間隔內(nèi)相交的所有時空對象，如在土地利用變化地類流向分析中需查詢整個縣域在2009年和2013年這兩年間不同類型地類的面積變化；時空對象最近鄰居查詢指查找在指定時間間隔內(nèi)，離給定點（或區(qū)域）最近的一個或多個時空對象以及變化，如2005—2013年內(nèi)縣域內(nèi)某條公路沿線200 m鄰域內(nèi)的耕地增加、減少情況。土地變化分析的主體是圖斑，選取2005年、2008年、2009—2013年地類圖斑為檢索對象，對索引的查詢時間進行對比（時空數(shù)據(jù)查詢比較復(fù)雜，涉及索引結(jié)構(gòu)存儲策略、索引樹加載、頁面動態(tài)讀取、索引樹遍歷算法、索引的粗查、精煉查詢等），驗證其檢索效率?？臻g索引涉及2008年和2013年地類圖斑（基點現(xiàn)狀）合計160972條記錄，約306 M；2005—2008年、2009—2013年年度變更增量合計17320條記錄，約35.6 M。硬件平臺配置為Inter（R）Core（TM）2 Quad CPU Q9550，2.83 HZ，6 GB內(nèi)存，操作系統(tǒng)為Windows7 64位。針對上述幾種典型土地利用時空查詢情境，利用已建立的混合索引表重復(fù)進行時空檢索，記錄其索引消耗時間（隨機選取查詢區(qū)域500次，僅記錄查詢時間）。如表1所示。

表1可以看出，對于時空范圍、時空連接查詢、時空對象最近鄰居查詢等復(fù)雜空間查詢，其初查、精查的時間小于格網(wǎng)索引及HR樹索引，具有明顯優(yōu)勢。從索引結(jié)點分布可測算（圖5），行政區(qū)索引結(jié)點數(shù)與二級格網(wǎng)相當(dāng)，但不存在結(jié)點MBR切割要素、多處存儲情況，進而降低了索引存儲冗余度；同時，行政區(qū)索引結(jié)點按行政區(qū)布局，結(jié)點數(shù)比HR索引結(jié)點數(shù)低。因此，不考慮索引樹算法優(yōu)劣下，混合索引樹加載時間、頁面讀取時間優(yōu)于其他兩者。

為了進一步驗證索引查詢效率，本文從索引的時間復(fù)雜度角度進一步分析。為保證可比性，采用常用的二級格網(wǎng)索引，格網(wǎng)中的一級格數(shù)為S，每個格網(wǎng)中有s個結(jié)點對象。而行政區(qū)有M個，每個行政區(qū)下面對應(yīng)m個圖斑面狀對象。原則上認為M和S屬于同一個數(shù)量級。其中T為整個時間段（單位為a），t為查詢時間段（單位為a）。其中混合索引、格網(wǎng)索引、HR樹索引的結(jié)點分布圖如圖5（a）、（b）、（c）所示。

從表2分析可知，這6種典型的時空查詢情況下，混合索引的時間復(fù)雜度（O（S*log（m*T）））要分別小于格網(wǎng)索引的復(fù)雜度（O（S*s*T））以及HR樹索引的時間復(fù)雜度（O（M*log（m）*T））。這說明基于格網(wǎng)與HR樹的混合索引技術(shù)要比格網(wǎng)索引或HR樹索引的單獨使用查詢效率高。

多級格網(wǎng)索引在數(shù)據(jù)檢索時，只需簡單的地址運算就能檢索到對象所在結(jié)點，但是格網(wǎng)內(nèi)部缺少響應(yīng)的檢索機制，檢索效率會有影響?；旌纤饕诘讓痈窬W(wǎng)結(jié)點中分別構(gòu)建HR樹索引，這在一定程度上提高了格網(wǎng)內(nèi)部檢索效率；對于純粹的HR樹索引而言，樹的深度會直接影響檢索效率，在格網(wǎng)劃分的基礎(chǔ)上再進行HR樹索引，樹的深度會降低，涉及節(jié)點樹也相對有所減少，其檢索效率也會得到提升，重構(gòu)代價也比較小。另外，從空間復(fù)雜性來看，多級格網(wǎng)索引中對象會重復(fù)存儲在多個格網(wǎng)節(jié)點中，導(dǎo)致數(shù)據(jù)冗余。行政區(qū)在一定時間范圍內(nèi)具有穩(wěn)定性，以行政區(qū)為單位格網(wǎng)進行劃分可在一定程度上降低格網(wǎng)索引的后期維護成本。在格網(wǎng)內(nèi)部采用HR樹索引，這相比純粹的格網(wǎng)索引而言，大大降低了對格網(wǎng)大小的要求，解決了對象的重復(fù)存儲問題，提高了空間利用率。綜上所述，多級格網(wǎng)與HR樹的混合索引樹在檢索效率方面會有較好的性能，雖然其空間開銷會略大于HR樹，但是對于面向關(guān)系復(fù)雜、時間跨度大的長時間序列的土地利用時空數(shù)據(jù)而言，提高查詢速度、效率更為重要。

表2　時空檢索性能分析Tab.2　Spatio-temporal retrieval performance analysis

6　結(jié)束語

本文結(jié)合當(dāng)前長時間序列土地利用時空查詢的需求，提出基于地理網(wǎng)格分區(qū)與HR樹的時空混合索引方法，設(shè)計了時空索引結(jié)構(gòu)及相應(yīng)算法，實現(xiàn)了時空索引原型系統(tǒng)，表明了其可行性。以現(xiàn)狀圖斑、變更圖斑為研究對象，對混合索引實際檢索時間、存儲效率、檢索復(fù)雜度進行詳細分析，驗證了其在土地利用變化分析情境下的檢索技術(shù)優(yōu)勢。該混合索引機制解決了以往格網(wǎng)索引中結(jié)點重復(fù)存儲增加搜索難度的問題，同時保證了長時間序列土地利用時空數(shù)據(jù)查詢的檢索效率，為土地利用變化分析提供了可實現(xiàn)的技術(shù)方案。但本文提出的混合索引方法僅為初步實現(xiàn)，在索引數(shù)據(jù)加載、索引樹動態(tài)生成等算法還需進一步優(yōu)化；另外，當(dāng)土地利用年度變更極度不均衡時（局部年要素變化數(shù)據(jù)量大或者特別少），混合時空索引的效率還需進一步驗證。

（

）：

［1］ 李秀彬.土地利用變化的解釋［J］ .地理科學(xué)進展，2002，21（3）：195 - 203.

［2］ 程紅霞.土地利用變化的時空可視化分析方法研究［D］ .成都：西南交通大學(xué)，2010.

［3］ 李秀彬.對加速城鎮(zhèn)化時期土地利用變化核心學(xué)術(shù)問題的認識［J］ .中國人口·資源與環(huán)境，2009，（5）：1 - 5.

［4］ 彭朝冰，張禾裕，羅斌，等.我國土地空間數(shù)據(jù)挖掘應(yīng)用現(xiàn)狀與趨勢綜述［J］ .國土資源信息化，2013，（2）：33 - 36.

［5］ 朱炎，滕龍妹，徐財江，等.土地動態(tài)利用時空數(shù)據(jù)挖掘的方法及其實現(xiàn)［J］ .經(jīng)濟地理，2006，（S1）：124 - 127.

［6］ 徐財江，陳志榮，騰龍妹.土地利用時空數(shù)據(jù)管理與挖掘應(yīng)用研究［J］ .國土資源信息化，2008，（2）：3 - 6.

［7］ 阮淼釬，劉仁義，劉南，等.基于事務(wù)的土地利用時態(tài)統(tǒng)計模型研究［J］ .計算機應(yīng)用研究，2005，22（7）：31 - 33.

［8］ 萬遠，李霖，應(yīng)申，等.土地利用變化分析與決策系統(tǒng)的設(shè)計與實現(xiàn)［J］ .農(nóng)業(yè)工程學(xué)報，2011，27（6）：313 - 318.

［9］ Shashi Shekhar Sanjay Chawla. Spatial Database［M］ . 北京：機械工業(yè)出版社，2004.

［10］ Tao Yufei， Papadias Dimitris. Efficient historical R-trees［C］ . SSDBM，2001：223 - 232.

［11］ F Mokbel M.， M Ghanem T.， G Aref W. Spatio-temporal Access methods［J］ . IEEE Data Engineering Bulletin，2003，26（2）：40 - 49.

［12］ 張明波，陸鋒，申排偉，等. R樹家族的演變和發(fā)展［J］ .計算機學(xué)報，2005，28（3）：289 - 300.

［13］ J Nievergelt， H Hinterberger， C Sevcik K. The grid file：An adaptable symmetric multi key file structure［J］ . ACM Transactions on Database Systems， 1984， 9（1）：38 - 71.［14］ I Gargantini. An effective way to represent quadtrees［J］ . Communications of the ACM， 1982， 25（12）：905 - 910.

［15］ 李支成.時空數(shù)據(jù)庫復(fù)雜查詢方法研究［D］ .武漢：華中科技大學(xué)，2012.

［16］ 張林，湯大權(quán)，張翀.時空索引的演變與發(fā)展［J］ .計算機科學(xué)，2010，37（4）：15 - 20.

［17］ Nascimento Mario A.， Silva Jefferson RO. Towards historical R-trees［C］ . Acm Symposium on Applied Computing Sac， 1998.

［18］ Geraldo Zimbrao， Moreira Souza Jano. The temporal R-tree［J］ . Federal University of Rio de Janeiro， Brazil， 1998.

［19］ Kumar Anil， Tsotras Vassilis J.， Faloutsos Christos. Designing access methods for bitemporal databases［J］ . Knowledge and Data Engineering， IEEE Transactions on， 1998， 10（1）：1 - 20.

［20］ Theoderidis Y.， Vazirgiannis Michalis， Sellis Timos. Spatio-temporal indexing for large multimedia applications［C］ . International Conference on Multimedia Computing & Systems， 1996：441 - 448.

［21］ 李德仁，肖志峰，朱欣焰，等.空間信息多級網(wǎng)格的劃分方法及編碼研究［J］ .測繪學(xué)報，2006，35（1）：52 - 56.

［22］ 胡久鄉(xiāng)，何松，鐘瑜.空間數(shù)據(jù)庫網(wǎng)格索引機制的最優(yōu)劃分［J］ .計算機學(xué)報，2002，25（11）：1227 - 1230.

［23］ 肖偉器，馮玉才，繆勇武.空間對象數(shù)據(jù)庫的網(wǎng)格索引機制［J］ .計算機學(xué)報，1994，17（10）：736 - 742.

［24］ 郜允兵，潘瑜春，高秉博，等.面向土地利用調(diào)查的時空數(shù)據(jù)庫構(gòu)建技術(shù)研究［J］ .測繪科學(xué)，2015，（5）：49 - 54，88.

［25］ 朱會義，李秀彬.關(guān)于區(qū)域土地利用變化指數(shù)模型方法的討論［J］ .地理學(xué)報，2003，58（5）：643 - 650.

［26］ 吳敏君，陳天滋.基于分割聚類技術(shù)的R樹節(jié)點分裂方案［J］ .計算機應(yīng)用與軟件，2007，24（10）：42 - 44.

（本文責(zé)編：陳美景）

The Spatio-Temporal Indexing Technology Research of Long-time Series Land-use Data

GAO Yun-bing1，2，3， GAO Bing-bo2，3，4， LI Xiao-lan2，3，5， PAN Yu-chun2，3，4， ZHANG Xiao-dong1
（1. Institute of Information and Electrical Engineering， China Agricultural University， Beijing 100083， China； 2. Beijing Research Center for Information Technology in Agriculture， Beijing 100097， China； 3. National Engineering Research Center for Information Technology in Agriculture， Beijing 100097， China； 4. Key Laboratory of Agri-informatics， Ministry of Agricuture， Beijing 100097， China； 5. Beijing Engineering Research Center of Agricultural Internet of Things， Beijing 100097， China）

This paper aims to develop an efficient index technology for the change analysis and trend prediction of massive land-use spatio-temporal data， which was collected in the first and second national land survey. The main research way is that on the bases of analyzing grid index and HR index， this paper puts forward suitable mixed spatiotemporal index for the long-time series land-use data in the light of common scenarios about land-use data model. The results include 1） the index technology treats administrative boundaries as spatial grid， then uses the change investigatedyear as time scale to establish HR-tree index on the bases of grid index， and keeps the spatio-temporal objects of status bases and change increment as index nodes， thereby the hybrid spatio-temporal index structure based on grid and HR-tree is formed. 2） the paper describes related algorithms of index tree conformation， index query， index deletion and insertion in detail based on new index structure. The conclusion is that the paper discusses the time complexity with grid index， HR-tree index and the new hybrid index respectively in several typical scenarios cases of the land-use change analysis in Hannan area of Wuhan. It shows that hybrid index method has better query efficiency， and it meets the needs of land-use change spatio-temporal analysis.

land information； spatio-temporal data model； spatio-temporal index； grid index； HR-tree index； hybrid index

P208

A

1001-8158（2015）09-0034-08

10.11994/zgtdkx.2015.09.005

2015-05-28

2015-08-05

城鎮(zhèn)化發(fā)展用地時空監(jiān)管數(shù)據(jù)綜合處理與管理技術(shù)研究（2013BAJ05B01）。

郜允兵（1976-），男，河南焦作人，博士研究生。主要研究方向為時空數(shù)據(jù)索引及時空數(shù)據(jù)模型研究。E-mail： gaoyb@nercita.org.cn

李曉嵐（1988-），女，湖北麻城人，碩士。主要研究方向為土地利用空間分析。E-mail： lixl@nercita.org.cn