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

張子軒，萬定生，朱 凱

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

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

張子軒，萬定生，朱 凱

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

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

水利普查；數據多維；數據立方體；數據分析系統；層次維編碼片段

0 引 言

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

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

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

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

1.1 HDEFC思想

表1 水電站工程數據表

例1：表1生成的原始數據立方體由ADDVCD(水電站所在行政區劃代碼)、GCJB(水電站的工程級別)、JSQK(水電站建設情況)和KFFS(水電站開發方式)4個維度(簡稱A，G，J，K)和SL(數量)、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))個聚集單元。

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

表2 ADDVCD層次維編碼表

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

例2：以表1水電站工程數據簡表為例，采用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出現在元組1、2和3中，則G1的TID列表包含3項，即1、2和3。對這3個維中的屬性值建立倒排索引得到表3。

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

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

1.2 HDEFC生成算法

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

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

算法偽代碼如下所示：

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

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

方法：

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

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

將每個元祖的TID和MEASURE插入ID_measure數組；

if(維可分層){

利用二進制編碼創建層次維編碼表和TID關聯表；

}

else{

創建Di各屬性TID關聯表，即倒排索引；

}

}

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

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

}

1.3 HDEFC片段大小選擇

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

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

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

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

1.4 HDEFC查詢算法

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

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

詳細的算法偽代碼如下：

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

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

方法：

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

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

}

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

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

}

M←Bq∩ID_Measure

returnM

2 實驗結果與分析

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

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

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

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

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

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

圖2 存儲性能比較

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

3 系統設計與實現

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

圖3 水利普查數據分析系統

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

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

總之，該系統的開發研究，為水利普查數據分析提供了有效的平臺，以方便水利業務人員實現對于水利普查數據的二次加工和深度分析。

4 結束語

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

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

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

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

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

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

[11] 朱 凱,萬定生,程習鋒.水利普查成果分析中數據立方體計算研究[J].計算機與數字工程,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)；水利部公益性行業科研專項(201501022)

張子軒(1994-)，女，碩士研究生，研究方向為信息處理與信息系統；萬定生，教授，CCF會員，研究方向為信息處理與信息系統。

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