張子軒，萬(wàn)定生，朱 凱

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 210098)

層次維編碼片段立方體生成算法應(yīng)用研究

張子軒，萬(wàn)定生，朱 凱

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 210098)

數(shù)據(jù)量大、數(shù)據(jù)多維是水利普查數(shù)據(jù)的重要特征。根據(jù)水利普查決策分析的需要，在對(duì)數(shù)據(jù)立方體技術(shù)研究的基礎(chǔ)上，基于部分物化策略，提出了建立層次維編碼片段立方體(HDEFC)。利用維度屬性的概念分層特性，在層次維片段中采用混合索引(B-tree和Bit Code)技術(shù)對(duì)每個(gè)層次維的層次屬性進(jìn)行二進(jìn)制編碼，再利用生成的維度編碼代替原表中關(guān)鍵字，非層次維片段中采用倒排索引技術(shù)對(duì)每個(gè)片段子立方體進(jìn)行物化，減少了多表連接操作，從而提高OLAP查詢效率。實(shí)驗(yàn)結(jié)果表明，生成的HDEFC占用較小的存儲(chǔ)空間，查詢方法在面對(duì)高維的復(fù)雜查詢時(shí)具有優(yōu)勢(shì)。通過(guò)建立水利普查數(shù)據(jù)分析系統(tǒng)，說(shuō)明了該方法能夠有效地解決因數(shù)據(jù)量龐大、維度多導(dǎo)致的數(shù)據(jù)計(jì)算和查詢效率低下等問(wèn)題，降低了物化水利普查成果數(shù)據(jù)立方體的時(shí)間和空間成本。

水利普查；數(shù)據(jù)多維；數(shù)據(jù)立方體；數(shù)據(jù)分析系統(tǒng)；層次維編碼片段

0 引 言

隨著全國(guó)水利普查[1]工作的開展，形成了迄今最為全面細(xì)致、完整系統(tǒng)的涉水基礎(chǔ)數(shù)據(jù)資源和規(guī)范權(quán)威的水利普查成果數(shù)據(jù)，如何對(duì)這些普查成果數(shù)據(jù)進(jìn)行有效的分析與利用成為了制定正確水利建設(shè)方案的關(guān)鍵問(wèn)題。

數(shù)據(jù)倉(cāng)庫(kù)[2]作為一種新興技術(shù)被越來(lái)越多的領(lǐng)域所重視，數(shù)據(jù)挖掘[3-4]和聯(lián)機(jī)分析處理(OLAP)[5-6]都是基于數(shù)據(jù)倉(cāng)庫(kù)的分析工具。在OLAP中，數(shù)據(jù)通常以數(shù)據(jù)立方體(Data cube)[7]的方式存儲(chǔ)，數(shù)據(jù)立方體以“維度+度量”的方式組織數(shù)據(jù)，提供給分析人員多維的數(shù)據(jù)視圖，直觀地支持了OLAP中所需要的復(fù)雜多維分析。為節(jié)省存儲(chǔ)空間同時(shí)兼顧OLAP查詢效率，對(duì)數(shù)據(jù)立方體進(jìn)行預(yù)計(jì)算的有效方法可提高聯(lián)機(jī)分析處理能力。

結(jié)合水利普查數(shù)據(jù)量大、多維度、分層次的特征，文中以建立層次維編碼片段立方體(HDEFC)[8-9]為重心，采取能夠有效處理高維度的HDEFC生成算法和查詢算法，將其運(yùn)用于水利普查數(shù)據(jù)分析，并逐步實(shí)現(xiàn)OLAP、數(shù)據(jù)挖掘等功能。以水利普查中的水電站工程數(shù)據(jù)分析主題為例，利用層次維編碼片段立方體作為底層數(shù)據(jù)結(jié)構(gòu)，并展開了對(duì)水利普查數(shù)據(jù)分析與展示系統(tǒng)的建立與應(yīng)用研究。

1 層次維編碼片段立方體技術(shù)

1.1 HDEFC思想

表1 水電站工程數(shù)據(jù)表

例1：表1生成的原始數(shù)據(jù)立方體由ADDVCD(水電站所在行政區(qū)劃代碼)、GCJB(水電站的工程級(jí)別)、JSQK(水電站建設(shè)情況)和KFFS(水電站開發(fā)方式)4個(gè)維度(簡(jiǎn)稱A，G，J，K)和SL(數(shù)量)、ZJRL(水電站裝機(jī)容量)2個(gè)度量構(gòu)成，SK_Cube中包含16個(gè)聚集cuboids：{(A，G，J，K)，(*，G，J，K)，(A，*，J，K)，(A，G，*，K)，(A，G，J，*)，(*，*，J，K)，(*，G，*，K)，(*，G，J，*)，(A，*，*，K)，(A，*，J，*)，(A，G，*，*)，(*，*，*，K)，(*，*，J，*)，(*，G，*，*)，(A，*，*，*)，(*，*，*，*)}。維度ADDVCD中包含3個(gè)概念分層以及4個(gè)不同的屬性值，維度GCJB包含2個(gè)不同的屬性值，維度JSQK包含2個(gè)不同的屬性值，維度KFFS包含2個(gè)不同的屬性值，則將生成32((3+1)×2×2×2)個(gè)聚集cuboids和810((4+1)×(2+1)×(1+1)×(2+1)×(2+1)×(2+1))個(gè)聚集單元。

以水利普查對(duì)象中的行政區(qū)劃維ADDVCD為例，通過(guò)層次維編碼方法創(chuàng)建Province(省份)、City(城市)和County(區(qū)縣)這三個(gè)維度的層次編碼，并將其與事實(shí)表中記錄的TID進(jìn)行關(guān)聯(lián)。表1中ADDVCD維的編碼與水電站工程數(shù)據(jù)簡(jiǎn)表中各記錄的TID關(guān)聯(lián)關(guān)系如表2所示。

表2 ADDVCD層次維編碼表

定義3：層次維編碼片段立方體。對(duì)于一個(gè)具有n個(gè)維度的高維數(shù)據(jù)立方體C(D,M)，將維度集合{D1,D2,…,Dn}按照互不相交的原則，劃分為k個(gè)獨(dú)立的片段，其中層次維單獨(dú)劃分為一個(gè)片段，而非層次維劃分為大小為m的片段。對(duì)層次維中的層次屬性利用混合索引技術(shù)進(jìn)行二進(jìn)制編碼，然后用倒排索引技術(shù)[10]存儲(chǔ)非層次維片段中的聚集cuboids。這樣就將一個(gè)n維的立方體分割成k個(gè)低維的立方體,形成HDEFC。

例2：以表1水電站工程數(shù)據(jù)簡(jiǎn)表為例，采用HDEFC生成算法，立方體片段大小為3，則劃分出的HDEFC為(ADDVCD)，(GCJB，JSQK，KFFS)共2個(gè)片段，需要物化12((3+1)+2×2×2)個(gè)聚集cuboids和57((4+1)×(2+1)×(1+1)+(2+1)×(2+1)×(2+1))個(gè)聚集單元，所需存儲(chǔ)空間明顯減少。

定義4：非層次維倒排索引。對(duì)于HDEFC立方體中每個(gè)非層次維的每個(gè)屬性值，列出具有該值的所有元組的元組標(biāo)識(shí)符(TID)，形成非層次維的倒排索引。

例3：在表1中，非層次維有GCJB、JSQK、KFFS，對(duì)全部非層次維建立倒排索引。例如，屬性值G1出現(xiàn)在元組1、2和3中，則G1的TID列表包含3項(xiàng)，即1、2和3。對(duì)這3個(gè)維中的屬性值建立倒排索引得到表3。

至此，HDEFC立方體中層次維自成一個(gè)片段立方體，而非層次維片段立方體需要計(jì)算生成。表1中的非層次維恰好可以形成一個(gè)片段大小為3的立方體。

表3 由表1生成的非層次維倒排索引表

1.2 HDEFC生成算法

首先，將給定數(shù)據(jù)集(即基本方體)的所有維劃分成獨(dú)立的維群組，也可稱作立方體片段。其中每個(gè)層次維單獨(dú)為一個(gè)片段，數(shù)個(gè)非層次維組合成一個(gè)片段(關(guān)于非層次維的片段大小以及維分組將在下文進(jìn)行討論)。

掃描基本方體，并構(gòu)造每個(gè)維屬性的倒排索引。對(duì)于每個(gè)片段，計(jì)算完全局部(即基于片段的)數(shù)據(jù)立方體，而保留倒排索引。此外，對(duì)方體中每個(gè)單元保留倒排索引，即對(duì)于每個(gè)單元，記錄它的關(guān)聯(lián)TID列表。

算法偽代碼如下所示：

輸入：一個(gè)具有n個(gè)維度的立方體C：(D1,D2,…,Dn)。

輸出：片段劃分集合{F1,F2,…,Fk}和相對(duì)應(yīng)的局部片段立方體{HC1,HC2,…,HCk}；ID_measure數(shù)組。

方法：

將n維立方體C(D1,D2,…,Dn)分割成k個(gè)分段{F1,F2,…,Fk}；

for(i=1;i<=n;i++){

將每個(gè)元祖的TID和MEASURE插入ID_measure數(shù)組；

if(維可分層){

利用二進(jìn)制編碼創(chuàng)建層次維編碼表和TID關(guān)聯(lián)表；

}

else{

創(chuàng)建Di各屬性TID關(guān)聯(lián)表，即倒排索引；

}

}

for(每個(gè)非層次維片段Fi){

交叉計(jì)算同一Fi片段中的Di維對(duì)應(yīng)的TID列表值并計(jì)算其相應(yīng)的度量值，創(chuàng)建局部片段立方體HCi;

}

1.3 HDEFC片段大小選擇

HDEFC生成算法中，立方體片段大小的選擇顯得至關(guān)重要。片段過(guò)大會(huì)導(dǎo)致需要預(yù)聚集的立方體過(guò)多，從而增加存儲(chǔ)空間的負(fù)擔(dān)；片段過(guò)小會(huì)導(dǎo)致預(yù)聚集的立方體過(guò)少，從而無(wú)法滿足大部分的臨時(shí)聚集操作，增加響應(yīng)時(shí)間。必須在存儲(chǔ)空間和響應(yīng)時(shí)間中尋找最佳平衡點(diǎn)，即HDEFC片段最佳大小。

根據(jù)HDEFC生成算法的思想，假設(shè)某立方體共有S個(gè)維度，片段大小為L(zhǎng)，則每個(gè)片段將生成2L個(gè)立方體。將立方體片段大小L設(shè)為自變量x，因變量y為立方體總數(shù)量，得到函數(shù)(x>1)。

以水利普查中水庫(kù)工程為例，維度總數(shù)為19(行政區(qū)劃、流域水系、水資源區(qū)劃、水庫(kù)類型、擋水主壩類型按材料分、擋水主壩類型按結(jié)構(gòu)分、主要泄洪建筑物形式、工程建設(shè)情況、水庫(kù)調(diào)節(jié)性能、工程等別、主壩級(jí)別、重要保護(hù)對(duì)象、供水對(duì)象、水庫(kù)歸口管理部門、是否完成劃界、是否完成確權(quán)、工程任務(wù)、2011年供水量數(shù)據(jù)來(lái)源、主要擋水建筑物類型)，3個(gè)區(qū)域?qū)哟尉S自成片段，對(duì)剩下16個(gè)維度劃分立方體片段。

經(jīng)過(guò)研究得出，立方體數(shù)量隨著立方體片段大小的增加呈指數(shù)級(jí)增長(zhǎng)，即HDEFC存儲(chǔ)空間與立方體片段大小呈指數(shù)關(guān)系。考慮到立方體片段過(guò)小造成的臨時(shí)聚集時(shí)間增加這一可預(yù)見的事實(shí)，所以對(duì)于最佳立方體片段大小的選擇應(yīng)該是3或4為宜。

1.4 HDEFC查詢算法

通常的查詢類型包括點(diǎn)查詢[11]、范圍查詢[6]和冰山查詢[12]。由于HDEFC定位于水利普查高維數(shù)據(jù)查詢，現(xiàn)在基于HDEFC結(jié)構(gòu)模型，采用范圍查詢方法進(jìn)行有效查詢處理。

以范圍查詢?yōu)槔?，HDEFC范圍查詢算法可以被分解成多個(gè)點(diǎn)查詢，在范圍查詢中，立方體至少存在一個(gè)維度di，其取值不唯一。該算法核心在于將查詢條件中的維度條件分解整理后，找出同一HDEFC片段中的維度，分別從不同的HDEFC片段中查詢出符合查詢條件的TID列表，最終再對(duì)各TID列表進(jìn)行求交。

詳細(xì)的算法偽代碼如下：

輸入：立方體片段集合{HC1,HC2,…,HCk}；ID_measure數(shù)組；形式的范圍查詢。

輸出：基于范圍查詢的結(jié)果度量。

方法：

for(i=1;i<=k;i++){

Bqi←運(yùn)用點(diǎn)查詢算法得到每個(gè)點(diǎn)查詢的相交集合;

}

if(存在至少一個(gè)非空Bqi){

Bq←{Bq1,Bq2,…,Bqk}集合求交得到最終集合;

}

M←Bq∩ID_Measure

returnM

2 實(shí)驗(yàn)結(jié)果與分析

本節(jié)在不同大小的數(shù)據(jù)集上對(duì)文中提出的HDEFC生成算法進(jìn)行性能比較。實(shí)驗(yàn)硬件環(huán)境：處理器為Intel(R)Core(TM)i5-4750CPU@ 3.40GHz，內(nèi)存為4GB，硬盤為640GB、7 200rpm。軟件環(huán)境：操作系統(tǒng)為Win7，數(shù)據(jù)庫(kù)為SQLServer2005，編程語(yǔ)言為Java，平臺(tái)為Eclipse。

實(shí)驗(yàn)采用水利基本情況普查中的水電站工程對(duì)象數(shù)據(jù)，記錄數(shù)為98 000，對(duì)基本表進(jìn)行整理后選取18個(gè)維度屬性和10個(gè)度量屬性，并在實(shí)驗(yàn)前對(duì)各數(shù)據(jù)進(jìn)行了規(guī)范化處理。各實(shí)驗(yàn)中每個(gè)片段大小為3。

圖1是層次維編碼相對(duì)簡(jiǎn)單位圖索引的壓縮比(坐標(biāo)經(jīng)過(guò)處理)。

圖1 層次維編碼相對(duì)簡(jiǎn)單位圖索引的壓縮比

從圖中可以看出，當(dāng)維成員個(gè)數(shù)為256時(shí)，簡(jiǎn)單位圖索引需要256bits，而層次維編碼位數(shù)只需8bits，數(shù)據(jù)壓縮比為256/8=32。隨著維成員數(shù)量的持續(xù)增加，數(shù)據(jù)壓縮比將進(jìn)一步增大。

圖2展示了基本事實(shí)表記錄數(shù)對(duì)數(shù)據(jù)立方體存儲(chǔ)空間的影響。

圖2 存儲(chǔ)性能比較

總的來(lái)說(shuō)，HDEFC方法所需的存儲(chǔ)空間整體小于簡(jiǎn)單原始的外殼片段立方體(Minimalcubing)[13-14]方法。隨著記錄數(shù)的增加，HDEFC方法中層次維編碼高壓縮性的特點(diǎn)就表現(xiàn)得更加明顯，且所需存儲(chǔ)空間的增長(zhǎng)趨勢(shì)相對(duì)緩慢。實(shí)驗(yàn)結(jié)果表明，HDEFC方法能夠有效減少立方體存儲(chǔ)空間，相對(duì)Minimalcubing方法具有一定優(yōu)勢(shì)。

3 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

依據(jù)文中所述的層次維編碼片段立方體技術(shù)，系統(tǒng)進(jìn)行了相應(yīng)的數(shù)據(jù)庫(kù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)設(shè)計(jì)。開發(fā)與部署主要運(yùn)用了JSP和GROOVY技術(shù)，其中前臺(tái)使用JSP技術(shù)進(jìn)行界面展示，后臺(tái)與SQLServer數(shù)據(jù)庫(kù)的連接使用GROOVY語(yǔ)言，再結(jié)合ArcGIS平臺(tái)對(duì)水利普查數(shù)據(jù)進(jìn)行地圖可視化展示。文中所構(gòu)建的水利普查層次維編碼片段數(shù)據(jù)立方體在系統(tǒng)運(yùn)行過(guò)程中表現(xiàn)出顯著的優(yōu)勢(shì)，比如對(duì)水利普查數(shù)據(jù)維度的分析與查詢響應(yīng)時(shí)間在該系統(tǒng)中得到了高效的實(shí)現(xiàn)，給用戶帶來(lái)了極大方便。圖3顯示了水利普查數(shù)據(jù)分析與展示信息結(jié)果。

圖3 水利普查數(shù)據(jù)分析系統(tǒng)

該系統(tǒng)實(shí)現(xiàn)了水利普查成果展示、水利普查基礎(chǔ)數(shù)據(jù)查詢、水利普查主題查詢、空間分布以及文檔資料等功能，能夠?qū)λ詹閿?shù)據(jù)進(jìn)行查詢與展示，可以有效地分析水利普查成果數(shù)據(jù)，進(jìn)而進(jìn)行決策分析。該系統(tǒng)運(yùn)用信息可視化技術(shù)，建立了可交互的友好美觀的用戶界面，能有效地查詢水利普查對(duì)象地理信息與具體信息。

水利普查數(shù)據(jù)分析系統(tǒng)還加入了“水利普查主題展示”的概念，在水利普查對(duì)象的大環(huán)境中以用戶關(guān)注點(diǎn)為中心，進(jìn)行單類對(duì)象多指標(biāo)以及多類對(duì)象相關(guān)指標(biāo)的主題定制展示。

總之，該系統(tǒng)的開發(fā)研究，為水利普查數(shù)據(jù)分析提供了有效的平臺(tái)，以方便水利業(yè)務(wù)人員實(shí)現(xiàn)對(duì)于水利普查數(shù)據(jù)的二次加工和深度分析。

4 結(jié)束語(yǔ)

在介紹水利普查數(shù)據(jù)特征的基礎(chǔ)上，文中提出了適用于高維水利普查數(shù)據(jù)分析的部分物化立方體結(jié)構(gòu)—HDEFC，以具有代表性的水電站工程數(shù)據(jù)為例，就HDEFC的生成算法、查詢算法和立方體片段大小選擇進(jìn)行了探究，并構(gòu)建了水利普查數(shù)據(jù)分析系統(tǒng)。此系統(tǒng)能夠滿足對(duì)水利普查數(shù)據(jù)分析的基本要求，且數(shù)據(jù)分析查詢響應(yīng)速度快于一般數(shù)據(jù)倉(cāng)庫(kù)的多維數(shù)據(jù)分析系統(tǒng)。通過(guò)實(shí)驗(yàn)進(jìn)一步驗(yàn)證了提出的HDEFC方法在水利普查數(shù)據(jù)分析領(lǐng)域的適用性。相比于目前數(shù)據(jù)分析系統(tǒng)中普遍采用的低維度少度量的處理方式，得益于HDEFC的底層立方體結(jié)構(gòu)和相應(yīng)的查詢方式，可以靈活地進(jìn)行高維度多度量的查詢和分析，為水利決策者提供了更加廣闊的數(shù)據(jù)視野。

[1] 龐進(jìn)武,程益聯(lián),羅志東.水利普查與信息化[J].水利信息化,2012(1):19-22.

[2] 占 軍,萬(wàn)定生,李 宇.基于Oracle數(shù)據(jù)倉(cāng)庫(kù)的水利普查數(shù)據(jù)展現(xiàn)系統(tǒng)[J].計(jì)算機(jī)與數(shù)字工程,2012,40(10):55-57.

[3] 楊嘉杰.水量水費(fèi)數(shù)據(jù)立方體的OLAP和數(shù)據(jù)挖掘技術(shù)研究[D].廣州:中山大學(xué),2012.

[4] 尹 濤,關(guān)興中,萬(wàn)定生.數(shù)據(jù)挖掘技術(shù)在水文數(shù)據(jù)分析中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(12):4721-4725.

[5]ChaudhuriS,DayalU.AnoverviewofdatawarehousingandOLAPtechnology[J].ACMSIGMODRecord,1997,26(1):65-74.

[6]HoCT,AgrawalR,MegiddoN,etal.RangequeriesinOLAPdatacubes[J].ACMSIGMODRecord,1970,26(2):73-88.

[7]GrayJ,ChaudhuriS,BosworthA,etal.Datacube:arelationalaggregationoperatorgeneralizinggroup-by,cross-tab,andsub-totals[J].DataMiningandKnowledgeDiscovery,1997,1:29-53.

[8]MarklV,RamsakF,BayerR.ImprovingOLAPperformancebymultidimensionalhierarchicalclustering[C]//ProcofIDEAS’99.[s.l.]:[s.n.],1999:165-177.

[9] 胡孔法,董逸生,徐立臻,等.一種基于維層次編碼的OLAP聚集查詢算法[J].計(jì)算機(jī)研究與發(fā)展,2004,41(4):608-614.

[10] 林俊鴻,姜 琨,楊岳湘.倒排索引查詢處理技術(shù)[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(3):572-575.

[11] 朱 凱,萬(wàn)定生,程習(xí)鋒.水利普查成果分析中數(shù)據(jù)立方體計(jì)算研究[J].計(jì)算機(jī)與數(shù)字工程,2014,42(9):1591-1594.

[12]FangM,ShivakumarN,Garcia-MolinaH,etal.Computingicebergqueriesefficiently[C]//Internationalconferenceonverylargedatabases.NewYork:[s.n.],1999.

[13]LiX,HanJ,GonzalezH.High-dimensionalOLAP:aminimalcubingapproach[C]//Proceedingsofthethirtiethinternationalconferenceonverylargedatabases.[s.l.]:[s.n.],2004:528-539.

[14]LiC,CongG,TungAKH,etal.Incrementalmaintenanceofquotientcubeformedian[C]//ProceedingsofthetenthACMSIGKDDinternationalconferenceonknowledgediscoveryanddatamining.Washington:ACM,2004:226-235.

Application Research on Hierarchical Dimension Encoding Fragment Cube Algorithm

ZHANG Zi-xuan，WAN Ding-sheng，ZHU Kai

(College of Computer and Information,Hohai University,Nanjing 210098,China)

Large amount of and multidimensional data is an important feature of water census data.According to the need of water census decision analysis,on the basis of data cube technology and partial materialization strategy,the establishment of Hierarchical Dimension Encoding Fragment Cube (HDEFC) is put forward.By the concept hierarchy characteristics of the dimension attribute,hybrid index (B-tree and Bit Code) technology is used to execute binary coding for hierarchy properties of each dimension,and the generated dimension code is applied to replace the key in the original table.In addition,non hierarchical dimension fragment uses inverted index technology to materialize each sub cube,so as to reduce the multi table join operation and improve OLAP query efficiency.Experiments show that the generated HDEFC occupies less storage space,and the query method has advantages in the face of high dimensional complex query.Through the establishment of water census data analysis system show that the method can effectively solve the problem of low efficiency of data calculation and query because of the huge amount of and multi-dimensional data,which reduces the cost of time and space of the material of water census results data cube.

water census;multi-dimensional data;data cube;data analysis system;hierarchical dimension encoding fragment

2016-04-08

2016-08-02

時(shí)間：2017-01-10

國(guó)家科技支撐計(jì)劃課題(2015BAB07B01)；水利部公益性行業(yè)科研專項(xiàng)(201501022)

張子軒(1994-)，女，碩士研究生，研究方向?yàn)樾畔⑻幚砼c信息系統(tǒng)；萬(wàn)定生，教授，CCF會(huì)員，研究方向?yàn)樾畔⑻幚砼c信息系統(tǒng)。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1019.058.html

TP391

A

1673-629X(2017)02-0134-05

10.3969/j.issn.1673-629X.2017.02.030