一種用于時空體元編解碼存儲的低計算量優(yōu)化方法*

顧清華，馬 龍，盧才武

(西安建筑科技大學(xué)管理學(xué)院，陜西西安710055)

1 引言

近年來，地理信息系統(tǒng)受大數(shù)據(jù)環(huán)境的深入影響，時間變化的信息存儲管理備受關(guān)注［1］。時態(tài)地理信息系統(tǒng)TGIS(Temporal Geography Information System)組織的重點(diǎn)是時空數(shù)據(jù)庫STDB(Spatio-Temporal Data Base)［2］。時空體元作為 TGIS 中實體對象表達(dá)的最小單元，可動態(tài)反映地理空間內(nèi)的事物，這就需要存儲海量的時間和空間屬性的數(shù)據(jù)，且這些數(shù)據(jù)需能在有限的存儲空間和傳輸速率下實現(xiàn)存儲轉(zhuǎn)換和表示計算。如何降低這些海量數(shù)據(jù)的存儲計算量則成為了解決這些問題的關(guān)鍵。目前，為了減少時空數(shù)據(jù)存儲空間，降低數(shù)據(jù)傳輸計算量，時空數(shù)據(jù)索引結(jié)構(gòu)、數(shù)據(jù)編碼和存儲方法的優(yōu)劣直接影響著STDB和TGIS的整體性能，它是解決二者之間數(shù)據(jù)存儲轉(zhuǎn)換、編解碼過程計算量的關(guān)鍵技術(shù)。

十六叉樹HDT(HexaDecimal Tree)索引結(jié)構(gòu)最早是由Inamoto［3］在1993年提出的，經(jīng)過不斷的實踐應(yīng)用，該方法成為TGIS數(shù)據(jù)索引的關(guān)鍵技術(shù)［4］，實踐證明其對海量時空數(shù)據(jù)索引、查詢具有突出的特點(diǎn)，因此利用四維十六叉樹索引結(jié)構(gòu)建立時空數(shù)據(jù)索引在需求上是完全合理的。但是，在十六叉樹索引結(jié)構(gòu)中仍是采用十進(jìn)制對時空對象進(jìn)行編碼，這既無法滿足計算機(jī)存儲管理要求，又增加了時空數(shù)據(jù)存儲、轉(zhuǎn)換和傳輸過程的計算量。為此，Lacan 等與 Plank［5，6］采用傳統(tǒng)的范德蒙碼和柯西碼，構(gòu)建了伽羅華有限域上的時空數(shù)據(jù)存儲系統(tǒng)和編碼方法。但是，在實際應(yīng)用中，這兩種方法在編解碼轉(zhuǎn)換時存儲開銷大，兼容性差，并需借助查詢乘法表來完成域內(nèi)體元乘法運(yùn)算。Wardlaw與Plank 等［7，8］采用二進(jìn)制矩陣表示域內(nèi)體元，構(gòu)建了二進(jìn)制矩陣上的編碼方法，從而使存儲的體元數(shù)據(jù)編解碼過程具有更低的計算優(yōu)勢。但是，如何進(jìn)一步降低時空體元對象編解碼過程中的計算量，學(xué)術(shù)界只進(jìn)行了簡單的探索，并未形成完整的解決方案。李德仁等［9］針對地理空間體元計算的復(fù)雜性問題，采用一種新的網(wǎng)格分裂方法，實現(xiàn)了空間對象網(wǎng)格編碼策略、存儲方法以及地球空間坐標(biāo)的轉(zhuǎn)換方法。郭達(dá)志等［10］根據(jù)時態(tài)GIS的應(yīng)用需求，構(gòu)建了四維時空數(shù)據(jù)模型，解決了時空對象線性編碼、存儲計算和時空坐標(biāo)轉(zhuǎn)換問題。但是，這些索引結(jié)構(gòu)、編解碼和存儲方法均有各自的適用范圍，對于時變范圍較大或存在多個局部極小點(diǎn)的數(shù)據(jù)索引、存儲表示計算量還大。因此，本文根據(jù)地理空間實體動態(tài)變化特征，提出了一種用于時空網(wǎng)格體元模型編解碼存儲的低計算量優(yōu)化方法，通過對網(wǎng)格體元對象的編碼表示和存儲轉(zhuǎn)換，構(gòu)建了時空網(wǎng)格體元編解碼優(yōu)化方法，使得網(wǎng)格體元模型在時空數(shù)據(jù)庫中存儲、表示、轉(zhuǎn)換和數(shù)據(jù)傳輸過程中的計算量進(jìn)一步降低，并對時空網(wǎng)格體元編解碼的時空復(fù)雜度和優(yōu)化算法進(jìn)行分析。最后的實驗結(jié)果表明，本文提出的方法可有效降低編解碼存儲過程中約30%左右的計算量。

2 時空網(wǎng)格體元編碼及轉(zhuǎn)換方法

2．1 時空網(wǎng)格體元編碼和解碼模型

十六叉樹本質(zhì)上是對目標(biāo)網(wǎng)格體元的動態(tài)存儲方式，也是實現(xiàn)體元編解碼表示和數(shù)據(jù)索引的結(jié)構(gòu)。由十六叉樹編碼圖解［10］可知，該索引結(jié)構(gòu)對于空間體元對象標(biāo)識與地理時空坐標(biāo)位置上存在著嚴(yán)格的對應(yīng)關(guān)系，可較好地實現(xiàn)地理時空對象編解碼的轉(zhuǎn)換與計算。時空網(wǎng)格體元對象的解碼數(shù)學(xué)模型為:

其中，ci、di、ei、fi(i=n －1，n －2，…，0) 的取值為0或1，分別為 X、Y、Z、T軸上坐標(biāo)值所對應(yīng)在網(wǎng)格體元中的解碼值權(quán)系數(shù)，p為網(wǎng)格體元分裂的次數(shù)或分辨率。

每個十六叉樹節(jié)點(diǎn)的編碼采取的形式為qn－1，qn－2，…，0。每個位置上的 qi是從(0，1，…，10，A，…，F(xiàn))十六個數(shù)中取其中之一，qi的個數(shù)取決于上述分辨率p。時空網(wǎng)格體元對象的編碼數(shù)學(xué)模型為:

其中，qi為編碼值，ci、di、ei、fi分別為 X、Y、Z、T 軸上坐標(biāo)值所對應(yīng)網(wǎng)格體元的編碼數(shù)據(jù)權(quán)系數(shù)。

2．2 時空網(wǎng)格體元編碼存儲轉(zhuǎn)換

對地理時空網(wǎng)格體元對象編解碼后還需滿足系統(tǒng)存儲要求，即將用十進(jìn)制表示的空間實體對象轉(zhuǎn)換為二進(jìn)制形式。因此，本文借助高斯坐標(biāo)的3DGIS編碼方法［11］，設(shè)計出符合地理網(wǎng)格體元對象編碼存儲轉(zhuǎn)換方法，其轉(zhuǎn)換步驟如下:

Step 1定義時空區(qū)域參照基點(diǎn)O(x0，y0，z0，t0)。

Step 2定義固定時間t周期內(nèi)沿著X、Y、Z軸的網(wǎng)格體分割尺寸 Dx、Dy、Dz，結(jié)合十六叉樹原理［10］，通常 Dx、Dy、Dz定義為2nm(n=1，…，10)，Dt定義為日期型數(shù)據(jù)。且根據(jù)研究區(qū)域內(nèi)空間實體對象的變異頻度和復(fù)雜度來確定n:當(dāng)變異頻度很高時，可選擇低值(n=0，1);當(dāng)變異頻度適中時，可選擇中值(n=2，3);當(dāng)變異頻度很低時，可選擇高值(n=4，5)，t選取為采樣數(shù)據(jù)的時刻。

Step 3按規(guī)定尺寸(Dx×Dy×Dz)和給定的時間點(diǎn)，把目標(biāo)網(wǎng)格體元區(qū)域劃分為四維空盒集，如圖1所示;劃分后的目標(biāo)區(qū)域內(nèi)網(wǎng)格體編碼可以采用時空網(wǎng)格體元編碼模型(如式(2)所示)，如圖2所示。

Step 4計算任意地理空間實體對象A的二進(jìn)制編碼:

(1)定義實體對象A的近基點(diǎn)A0:實體對象的最小包圍盒的最近角點(diǎn)為近基點(diǎn)A0(x，y，x)，其表達(dá)式為min［(x－x0)2+(y－y0)2+(z－z0)2］;當(dāng)存在兩個以上的近基點(diǎn)時，任選其一。

(2)計算近基點(diǎn)A0空盒集區(qū)域的行號I(沿X軸)、列號J(沿Y軸)和層級號(沿Z軸)以及時間點(diǎn)編號，其計算表達(dá)式參考文獻(xiàn)［12］。

(3)將近基點(diǎn)A0所在空盒的十進(jìn)制行列層次號(I，J，K)轉(zhuǎn)換為二進(jìn)制行列層次號(I'，J'，K')。

(4)獲取二進(jìn)制行列層次號(I'，J'，K')中每一位二進(jìn)制數(shù) Pit、Pjt、Pkt，及時間編號:

其中，＆ 為“與”操作符，t為位的序號，t=1，2，3，…，n。

(5)基于二進(jìn)制行列層次號(I'，J'，K')計算時空實體對象A所在空盒的二進(jìn)制Morton碼:

3 時空網(wǎng)格體元編解碼計算優(yōu)化

3．1 二進(jìn)制解碼矩陣構(gòu)建

根據(jù)Wardlaw有限域空間體元方法［6］，如果采用B0表示有限域網(wǎng)格體元對應(yīng)的二進(jìn)制矩陣，則構(gòu)建的二進(jìn)制解碼矩陣的形式為:

其中，Bxk∈{B0，B1，B2，…，B2m－1}。

由矩陣的性質(zhì)可知，對矩陣行列變換后，矩陣的秩不變，將R矩陣轉(zhuǎn)化為如下的形式:

其中，Im為m×m的單位矩陣;I為(m×k)×(m×k)的單位矩陣;Vij為由0、1構(gòu)成的m×m方陣;V'是(m×r)×(m×k)的0、1矩陣。

因為 Vi1，…，Vik是一個由 0、1構(gòu)成的 m ×(m ×k)矩陣，［Vi1，…，Vik］是由 1×(m ×k)階的0、1構(gòu)成的行向量，由此可將十進(jìn)制表示的體元對象編解碼換算為二進(jìn)制形式，從而實現(xiàn)網(wǎng)格體元數(shù)據(jù)塊的校驗和容錯。

在二進(jìn)制碼存儲的過程中，檢驗網(wǎng)格體元數(shù)據(jù)塊將行向量中體元1對應(yīng)的所有網(wǎng)格體元數(shù)據(jù)塊之間進(jìn)行異或運(yùn)算，進(jìn)而獲取校驗的網(wǎng)格體元數(shù)據(jù)塊(圖2中陰影劃分塊部分)。具體計算過程如圖3所示。

3．2 時空網(wǎng)格體元編碼與解碼過程的低計算量優(yōu)化算法

在實際的應(yīng)用過程中，借助二進(jìn)制編碼矩陣的存儲方法，采用異或運(yùn)算實現(xiàn)編解碼的校驗和容錯，降低整個網(wǎng)格體元編解碼存儲的計算量。其總體優(yōu)化思路:首先通過Wardlaw的方法構(gòu)造有限域體元的二進(jìn)制編碼矩陣;然后根據(jù)網(wǎng)格體元校驗塊最優(yōu)次序算法，依次計算出二進(jìn)制編碼矩陣中各向量間的關(guān)系;最后依據(jù)校驗塊優(yōu)化計算方法，先計算出由向量本身確定的校驗塊異或計算次數(shù)，再從已知向量的校驗塊間接搜索計算出其余向量的未知校驗塊。通過減少向量間的校驗塊計算的異或次數(shù)，從而降低整個網(wǎng)格體元編碼存儲過程中的計算量。反向計算過程，即是解碼過程的優(yōu)化方法。

設(shè)任意網(wǎng)格體元編碼矩陣形式如式(7)所示:

則可根據(jù)生成的校驗塊Vrm中的行向量l1，l2，…，lrm為“1”的數(shù)量確定出異或計算次數(shù)。其優(yōu)化算法的流程如圖4所示。

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

4．1 數(shù)據(jù)來源

為了驗證本文所提出的時空體元對象編解碼、存儲過程計算量算法的有效性，使用SURPAC礦業(yè)軟件對某礦山的經(jīng)緯度坐標(biāo)和礦床高程數(shù)據(jù)進(jìn)行處理后，獲得該礦山某采場的礦體空間塊體數(shù)據(jù)模型，時間屬性以采剝與否的實際時間為基準(zhǔn)，并對復(fù)雜礦體模型數(shù)據(jù)進(jìn)行簡化處理，選取礦床中部分塊體的地理時空坐標(biāo)數(shù)據(jù)集(X，Y，Z，T)={(6，3，4，1)，(0，2，3，1)，(2，1，0，0)，(2，0，2，0)}作為典型實驗數(shù)據(jù)，采用SURPAC軟件處理的體元數(shù)據(jù)模型如圖5所示。

4．2 時空網(wǎng)格體元數(shù)據(jù)編解碼

由2．1節(jié)介紹的時空網(wǎng)格體元對象編解碼的數(shù)學(xué)模型可知，選取空間分辨率n=3，時間點(diǎn)t=0時，表示不開采，其空間坐標(biāo)(X，Y，Z)分別為(2，1，0)、(2，0，2);時間點(diǎn) t=1 時，表示開采，其空間坐標(biāo)(X，Y，Z)分別為(6，3，4)、(0，2，3)。將這兩組數(shù)據(jù)集代入模型(2)中可獲得四組不同的編碼值(或定位碼);反之，根據(jù)給定的解碼值與網(wǎng)格體元數(shù)據(jù)權(quán)系數(shù)，將對應(yīng)的編碼值代入模型(1)中，可計算出對應(yīng)的解碼值。詳細(xì)計算結(jié)果如表1與圖2有灰色填充標(biāo)識的體元所示。

Table 1 Encoding and decoding of spatiotemporal grid voxel data表1 時空網(wǎng)格體元數(shù)據(jù)編解碼表

4．3 數(shù)據(jù)編碼存儲轉(zhuǎn)換方法

根據(jù)2．2節(jié)可知，網(wǎng)格體元編解碼是十進(jìn)制表示形式，需要將其轉(zhuǎn)換為二進(jìn)制形式，并需確定目標(biāo)網(wǎng)格體元的高斯坐標(biāo)的基點(diǎn)和近基點(diǎn)。本文選取時間點(diǎn) t=1，解碼值為(X，Y，Z)=(6，3，4)所在的目標(biāo)區(qū)域為例，其對應(yīng)的基點(diǎn)值為O(5 433 903．01，2 073 356．22，－200．0)，實體對象 A 的近基點(diǎn)為 A0(543 721．73，2 073 464．85，－332．1)。定義Dx=Dy=26m=64 m，Dz=24m=16 m。則其對應(yīng)的 I、J、K 及 MT 碼如下:

其中，函數(shù)INT()表示向上取值。

4．4 時空網(wǎng)格體元編解碼低計算量優(yōu)化算法

4．4．1 網(wǎng)格體元解碼

由3．2 節(jié)可知，依然以時間點(diǎn) t=1，(X，Y，Z)=(6，3，4)為例，選取構(gòu)造有限域元素參數(shù)m=3，根據(jù) Plank等人［13］提出的二進(jìn)制矩陣構(gòu)造方法，隨機(jī)選取3個二進(jìn)制矩陣B1、B2、B5，則構(gòu)造的二進(jìn)制矩陣如式(8)、式(9)所示:

矩陣R優(yōu)化后:

其中，I為9×9的單位矩陣，V'如式(11)所示;

根據(jù)空間坐標(biāo)(6，3，4)的二進(jìn)制解碼矩陣R中的子矩陣 V'，可確定向量 l1，l2，l3，…，l9，依據(jù)優(yōu)化算法需確定出編碼矩陣中各向量間的關(guān)系，如表2所示。其中，la(b)中a表示矩陣V'的行向量順序，b表示第a行向量生成校驗塊時的異或計算次數(shù)，((k×m－h(huán))/h)中k×m－h(huán)為矩陣V'中任意兩個向量間的相同體元位的個數(shù)，h為矩陣V'中任意兩個向量間的漢明距離;(x/y)表示任意兩個行向量li與li+1間相同體元個數(shù)x與不同體元個數(shù)y。

以上述解碼矩陣V'中第1、2行向量l1和l2為例，在表2中標(biāo)記為l1(3)與l2(4)，直接由l1和l2計算網(wǎng)格體元的校驗塊的異或次數(shù)分別為3和4，而向量所需校驗塊異或次數(shù)均小于由其它校驗塊間接計算的異或次數(shù)，即l3生成的校驗塊為p1，3可直接計算獲得;同理l1、l7、l8的校驗塊由對應(yīng)的行向量直接經(jīng)異或運(yùn)算獲得，即直接獲得的校驗數(shù)據(jù)塊分別為:

通過已計算獲得的網(wǎng)格體元校驗塊l1、l3、l7、l8可計算出其余向量對應(yīng)的體元校驗塊數(shù)據(jù)。從表2可知，從l1至其它行向量的漢明距離知，可由l1的校驗塊來計算出l9的體校驗數(shù)據(jù)塊，可由l8的校驗塊計算出l4的校驗塊，由于從l3、l6的校驗數(shù)據(jù)塊來確定l9的校驗數(shù)據(jù)塊需要更少的異或次數(shù)，因此，l1無法作為校驗其余行向量的基礎(chǔ)校驗數(shù)據(jù)塊。同理，l3、l7也無法作為基礎(chǔ)校驗數(shù)據(jù)塊。依次搜索，由圖6可知，分別通過l4的3次校驗數(shù)據(jù)塊異或次數(shù)計算出l5的校驗數(shù)據(jù)塊，l6的校驗數(shù)據(jù)塊可分別計算出l2、l9的校驗數(shù)據(jù)塊，即間接獲得的校驗數(shù)據(jù)塊分別為:

Table 2 Relationship of decoding vectors of spatiotemporal grid voxel data表2 時空網(wǎng)格體元數(shù)據(jù)解碼向量關(guān)系

至此解碼矩陣所生成的所有校驗數(shù)據(jù)塊計算結(jié)束，其整體計算流程如圖7所示。由此可知，將地理空間對象分裂為網(wǎng)格體元時，對其中的有形實體對象解碼所產(chǎn)生的存儲計算量較少，而對于地形中的“空”位置解碼就會造成大量的存儲計算。

4．4．2 網(wǎng)格體元編碼

對于時空網(wǎng)格體元數(shù)據(jù)解碼過程而言，當(dāng)存儲的體元數(shù)據(jù)丟失或毀壞時，可通過校驗矩陣K來恢復(fù)。因為基于矩陣K的解碼過程同樣需要通過完整的備份數(shù)據(jù)塊間的異或計算來恢復(fù)丟失數(shù)據(jù)，從線性分組碼的性質(zhì)知，解碼與編碼存在著嚴(yán)格的對應(yīng)轉(zhuǎn)換關(guān)系。因此，可直接將網(wǎng)格體元解碼矩陣與編碼矩陣進(jìn)行轉(zhuǎn)換，設(shè)編碼矩陣如式(12)所示，則校驗矩陣如式(13)所示:

矩陣K可用來恢復(fù)丟失的體數(shù)據(jù)塊，設(shè)存儲體數(shù)據(jù)塊B1，B2，…，Br的節(jié)點(diǎn)丟失，則隨機(jī)選擇k個節(jié)點(diǎn)備份的網(wǎng)格體元編碼數(shù)據(jù)塊對丟失數(shù)據(jù)進(jìn)行恢復(fù)。根據(jù)校驗矩陣K(k+r)×r恢復(fù)丟失掉的r個數(shù)據(jù)塊 B1，B2，…，Br，依據(jù)上述提出的校驗塊優(yōu)化計算方法將丟失的網(wǎng)格體元數(shù)據(jù)塊B1，B2，…，Br分別表示為X1，X2，…，Xr，并根據(jù)上述網(wǎng)格體元數(shù)據(jù)校驗塊最優(yōu)次序算法，將恢復(fù)過程中需要完整備份的編碼數(shù)據(jù)塊記為 Br+1，Br+2，…，Bk，Bk+1，…，Bk+r+1，Bk+r;令 φ = ［X1，X2，…，Xr，Dr+1，…，Dr+k］，其中 φ1=［X1，X2，…，Xr］;φ2=［Dr+1，…，Dr+k］。則根據(jù)關(guān)系式 φ．K(k+r)×r=0來恢復(fù)丟失的體數(shù)據(jù)塊。同樣，根據(jù)上述關(guān)系式中 φ與K(k+r)×r間的關(guān)系可以定位出丟失體數(shù)據(jù)塊在校驗矩陣K(k+r)×r中所對應(yīng)的向量，如果丟失的體數(shù)據(jù)塊所對應(yīng)的矩陣表示為K1r×r，校驗矩陣 K(k+r)×r中與完好備份的數(shù)據(jù)塊對應(yīng)的矩陣表示為K2r×r，那么有:

因為對于空間坐標(biāo)系(6，3，4)中網(wǎng)格體元解碼的恢復(fù)特征可知，系統(tǒng)最多可允許3個數(shù)據(jù)塊丟失，上述提出的算法恢復(fù)過程中假設(shè)原始網(wǎng)格體元數(shù)據(jù)全部丟失，只有完整的備份數(shù)據(jù)塊時，才可說明丟失數(shù)據(jù)塊的數(shù)據(jù)恢復(fù)過程。其中，

則通過式(18)確定的校驗矩陣行向量間的關(guān)系，其中，l'1，…，l'9表示丟失數(shù)據(jù)塊的向量順序，分別如表3與圖8所示。

通過圖8可獲得丟失數(shù)據(jù)塊的最優(yōu)計算次序，首先，計算由l1、l6、l7確定的丟失數(shù)據(jù)塊;其次，根據(jù)l2的數(shù)據(jù)塊，計算出由向量l8確定的丟失數(shù)據(jù)塊，同時根據(jù)l6數(shù)據(jù)塊，計算出l1數(shù)據(jù)塊;然后根據(jù)向量l8計算出l3數(shù)據(jù)塊，并根據(jù)向量l1計算出l4、l5的數(shù)據(jù)塊;最后根據(jù)恢復(fù)后的向量l3計算出l9確定的數(shù)據(jù)塊。其整體計算流程如圖9所示。

4．5 時空網(wǎng)格體元存儲過程的計算量分析

由于地理時空網(wǎng)格體元存儲形式可由二進(jìn)制矩陣表示，因此測試的數(shù)據(jù)集分別用不同規(guī)模的二進(jìn)制矩陣構(gòu)成。測試平臺所用的硬件為Intel core i5-4590M，3．3 GHz CPU，軟件為 Matlab2015R，時空網(wǎng)格體元數(shù)據(jù)分別為64×64、128×128、256×256的二進(jìn)制數(shù)值矩陣，十六叉樹的葉子節(jié)點(diǎn)數(shù)目分別為2 095、940、4 590、22 628 個，數(shù)值矩陣隨機(jī)生成。網(wǎng)格體元分裂時間和存儲效率如表4所示。

由圖2可知，假設(shè)將地理時空網(wǎng)格體從上至下劃分為三個子立方體區(qū)域，其中區(qū)域I為64×64，葉子節(jié)點(diǎn)數(shù)目分別為2 095個、940個，區(qū)域Ⅱ為128×128，葉子節(jié)點(diǎn)數(shù)目為4 590個、區(qū)域Ⅲ為256×256，葉子節(jié)點(diǎn)數(shù)目為22 628個。三個實驗區(qū)的時空網(wǎng)格體元編碼是從頂向下分裂方法產(chǎn)生十六叉樹，采用式(2)編碼，Morton編碼采用八叉樹的自頂向下分裂方法，可用式(4)編碼。

Table 3 Relationship of encoding vectors of spatiotemporal grid voxel data表3 時空網(wǎng)格體數(shù)據(jù)編碼向量關(guān)系

Table 4 Storage efficiency and splitting time of spatiotemporal grid voxel encoding and Morton encoding表4 時空網(wǎng)格體元編碼與Morton編碼的存儲效率與分裂時間

由表4的結(jié)果可知，分別采用以十六叉樹索引結(jié)構(gòu)和八叉樹索引結(jié)構(gòu)為基礎(chǔ)的兩種編碼方法，采用十六叉樹索引結(jié)構(gòu)對地理空間目標(biāo)塊體分裂所消耗的時間幾乎是采用八叉樹索引結(jié)構(gòu)的一半左右，隨著礦床塊體數(shù)量和葉子節(jié)點(diǎn)數(shù)量的增加，以八叉樹索引結(jié)構(gòu)的Morton編碼所消耗的分裂時間明顯增加。采用以十六叉樹索引結(jié)構(gòu)的網(wǎng)格體元編碼所占用的內(nèi)存空間要比采用八叉樹索引結(jié)構(gòu)的Morton編碼少25%左右，隨著礦床塊體數(shù)量和葉子節(jié)點(diǎn)數(shù)量的增加，兩種編碼方法占用的內(nèi)存空間成倍數(shù)增長。這是因為十六叉樹對目標(biāo)空間塊體的索引是以子立方體的形式分裂，而且分裂過程中會隨著時間區(qū)域的變化而不斷地釋放已訪問節(jié)點(diǎn)的內(nèi)存空間，而八叉樹索引結(jié)構(gòu)只是在同一立方體上對目標(biāo)空間塊體進(jìn)行遞歸分裂，分裂過程中已訪問節(jié)點(diǎn)由于根節(jié)點(diǎn)的關(guān)聯(lián)性而無法釋放，由此導(dǎo)致十六叉樹索引方法占用的存儲空間較少，分裂速度較快。同理，兩種編碼方法占用的外存空間也是以倍數(shù)在增長，網(wǎng)格體元編碼方法所占用的外存空間要明顯少于Morton編碼方法占用的外存空間。

4．6 低計算量優(yōu)化方法分析

為驗證提出的計算方法的通用性，分別對時間參數(shù) t=1 與空間參數(shù)為(6，3，4)，(0，2，3)以及時間參數(shù)為 t=0，空間參數(shù)為(2，1，0)，(2，0，2)的時空網(wǎng)格體元的編碼與解碼過程進(jìn)行了測試。上述編碼與解碼系統(tǒng)都由本文提出的方法構(gòu)建，其低計算量優(yōu)化性能如表5所示。

由表5可知，以構(gòu)建的(6，3，4)編碼矩陣為例，如果用傳統(tǒng)的分塊計算，需計算38次方可獲得全部校驗塊，而使用本文方法只需要計算26次，總的運(yùn)算次數(shù)減少31%左右。對于文中生成的9個校驗數(shù)據(jù)塊的編碼矩陣，每個校驗塊需要約2．9次異或運(yùn)算，因此極大地減少了計算量，從而大幅度地降低了計算時間，節(jié)約了存儲空間，其優(yōu)化后的編碼計算時間如圖10所示。

如果用傳統(tǒng)的塊計算方法進(jìn)行解碼，需要38次異或運(yùn)算恢復(fù)丟失的全部體數(shù)據(jù)塊，采用本文方法后，只需24次異或運(yùn)算，即總的運(yùn)算次數(shù)減少大約37%，因此極大地減少了恢復(fù)丟失數(shù)據(jù)的計算量，降低了時空復(fù)雜度。圖11所示為解碼過程計算時間的比較。同時，對表5中的二進(jìn)制解碼過程進(jìn)行了統(tǒng)計分析，由于缺失網(wǎng)格體編碼的數(shù)據(jù)塊不同，解碼過程也會有所差別。因此，將測試條件設(shè)置為所有原始塊體數(shù)據(jù)缺失，利用校驗數(shù)據(jù)塊對其進(jìn)行恢復(fù)，使用本文方法后，解碼過程的計算量大約減少30%。

Table 5 Computation comparison between encoding optimization and decoding optimization表5 編碼與解碼優(yōu)化計算量比較

5 結(jié)束語

在海量時空數(shù)據(jù)存儲和傳輸計算過程中，需要對動態(tài)產(chǎn)生的地理空間對象數(shù)據(jù)進(jìn)行存儲，本文提出的優(yōu)化計算方法可減少時空體元存儲過程中計算量的30%左右，系統(tǒng)響應(yīng)時間減少約50%。同時，該方法具有一定的通用性，凡是涉及時空體元編解碼存儲和二進(jìn)制矩陣確定的塊體異或運(yùn)算過程，均可采用該方法降低系統(tǒng)存儲過程中的計算量。但是，該方法只是針對已經(jīng)構(gòu)建的二進(jìn)制塊體矩陣的編解碼存儲過程進(jìn)行優(yōu)化，如何直接構(gòu)造出最低計算量的編解碼矩陣還需進(jìn)一步深入研究。