張子軒，萬定生，朱 凱

(河海大學 計算機與信息學院，江蘇 南京 210098)

層次維編碼片段立方體生成算法應用研究

張子軒，萬定生，朱 凱

(河海大學 計算機與信息學院，江蘇 南京 210098)

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

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

0 引 言

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

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

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

1 層次維編碼片段立方體技術

1.1 HDEFC思想

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

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

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

表2 ADDVCD層次維編碼表

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

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

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

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

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

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

1.2 HDEFC生成算法

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

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

算法偽代碼如下所示：

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

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

方法：

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

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

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

if(維可分層){

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

}

else{

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

}

}

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

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

}

1.3 HDEFC片段大小選擇

HDEFC生成算法中，立方體片段大小的選擇顯得至關重要。片段過大會導致需要預聚集的立方體過多，從而增加存儲空間的負擔；片段過小會導致預聚集的立方體過少，從而無法滿足大部分的臨時聚集操作，增加響應時間。必須在存儲空間和響應時間中尋找最佳平衡點，即HDEFC片段最佳大小。

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

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

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

1.4 HDEFC查詢算法

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

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

詳細的算法偽代碼如下：

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

輸出：基于范圍查詢的結果度量。

方法：

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

Bqi←運用點查詢算法得到每個點查詢的相交集合;

}

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

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

}

M←Bq∩ID_Measure

returnM

2 實驗結果與分析

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

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

圖1是層次維編碼相對簡單位圖索引的壓縮比(坐標經(jīng)過處理)。

圖1 層次維編碼相對簡單位圖索引的壓縮比

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

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

圖2 存儲性能比較

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

3 系統(tǒng)設計與實現(xiàn)

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

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

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

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

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

4 結束語

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

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

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

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

[4] 尹 濤,關興中,萬定生.數(shù)據(jù)挖掘技術在水文數(shù)據(jù)分析中的應用[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].計算機研究與發(fā)展,2004,41(4):608-614.

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

[11] 朱 凱,萬定生,程習鋒.水利普查成果分析中數(shù)據(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

時間：2017-01-10

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

張子軒(1994-)，女，碩士研究生，研究方向為信息處理與信息系統(tǒng)；萬定生，教授，CCF會員，研究方向為信息處理與信息系統(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