唐珊珊，萬定生，朱躍龍，余宇峰，朱 凱

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

水利普查成果數(shù)據(jù)立方體并行計(jì)算方法研究

唐珊珊，萬定生，朱躍龍，余宇峰，朱 凱

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

水利普查成果數(shù)據(jù)具有數(shù)據(jù)量大、維度多、維度分層等特點(diǎn)，因此物化水利普查成果數(shù)據(jù)立方體，所需的時間空間成本非常高。提出一種基于 Map/Reduce 計(jì)算模型進(jìn)行外殼片段立方體并行計(jì)算的新方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效地提高在大數(shù)據(jù)集上計(jì)算外殼片段立方體的效率，降低物化水利普查成果數(shù)據(jù)立方體的時間空間成本。將水利普查成果數(shù)據(jù)立方體應(yīng)用于多維分析系統(tǒng)，從多方面清晰直觀地展現(xiàn)水利普查成果數(shù)據(jù)。

水利普查；數(shù)據(jù)立方體；外殼片段立方體；Map/Reduce 技術(shù)

0 引言

水利普查是一項(xiàng)重大的國情國力調(diào)查，是國家資源環(huán)境調(diào)查的重要組成部分。開展水利普查是為了查清我國江河湖泊等的基本情況，建立國家基礎(chǔ)水信息平臺，展現(xiàn)水利普查成果數(shù)據(jù)，為國家經(jīng)濟(jì)社會發(fā)展提供科學(xué)可靠的基礎(chǔ)[1]。聯(lián)機(jī)分析處理（OLAP）向用戶提供及時分析數(shù)據(jù)以輔助決策，在OLAP 中數(shù)據(jù)通常以數(shù)據(jù)立方體（Data Cube）[2]形式存儲，數(shù)據(jù)立方體的物化可以大幅度減少查詢響應(yīng)時間，提高 OLAP 性能。但完全物化數(shù)據(jù)立方體通常需要非常高的空間和時間成本。為了提高數(shù)據(jù)立方體生成和查詢效率，許多專家學(xué)者提出了 Iceberg Cube[3]，Condensed Cube[4]和 Quotient Cube[5]等物化方法，這些方法在多維分析應(yīng)用中起著重要的作用。水利普查設(shè)計(jì)了 300 余項(xiàng)統(tǒng)計(jì)指標(biāo)，包括 8 大專題、33 小類、近 1 億個基本對象，使得水利普查成果數(shù)據(jù)具有覆蓋面廣、數(shù)據(jù)量大、維度多、維度分層等特點(diǎn)，數(shù)據(jù)維度可以達(dá)到 20 個，記錄數(shù)也常常超過 106條。因此物化水利普查成果數(shù)據(jù)立方體需要極高的時間空間成本[6]。

基于上述背景，提出一種基于 Map/Reduce 的外殼片段立方體并行計(jì)算方法，提高水利普查成果數(shù)據(jù)立方體物化效率，最后將生成的水利普查成果數(shù)據(jù)立方體應(yīng)用于多維分析系統(tǒng)展示。

1 水利普查成果數(shù)據(jù)立方體

1.1 水利普查成果數(shù)據(jù)主題設(shè)計(jì)

第一次全國水利普查涉及河流湖泊、水利工程、經(jīng)濟(jì)社會用水、河湖開發(fā)治理保護(hù)、水土保持和水利行業(yè)能力建設(shè)等情況及灌區(qū)和地下水取水井等8 大專題 33 小類近 1 億個基本對象，包括 300 余個指標(biāo)，2 000 余個普查數(shù)據(jù)項(xiàng)。經(jīng)過全國各級水利普查機(jī)構(gòu)審核、匯總分析等，形成了我國迄今最為全面細(xì)致、完整系統(tǒng)的涉水基礎(chǔ)數(shù)據(jù)資源和規(guī)范權(quán)威的水利普查成果數(shù)據(jù)。

根據(jù)中國水利水電科學(xué)研究院研制的《水利普查成果分析基本主題設(shè)計(jì)》報(bào)告，將水利普查成果數(shù)據(jù)基本主題設(shè)計(jì)按四級層次進(jìn)行規(guī)劃，一級主題為水利普查的 6 個專業(yè)方向，普查中的灌區(qū)專項(xiàng)和地下水井、水源地作為水利工程并入水利工程類中，二級主題為水利普查各類對象，三級主題為水利普查對象的屬性和關(guān)系分類主題，四級主題為分類主題下水利普查對象的主要指標(biāo)相關(guān)主題。直接分析主題總計(jì) 271 個（直接分析主題為最末級主題，以及沒有四級主題的三級主題（8 個）和四級主題（263 個）），水利普查基本主題表如表 1 所示。

表1 水利普查基本主題表

1.2 水利普查成果數(shù)據(jù)立方體設(shè)計(jì)

水利普查成果數(shù)據(jù)立方體數(shù)據(jù)模型的設(shè)計(jì)采用三級數(shù)據(jù)模型的方法，包括概念、邏輯和物理模型，分別對應(yīng)的設(shè)計(jì)結(jié)果為信息包圖、星型模型及物理數(shù)據(jù)模型等。

1）概念模型設(shè)計(jì)。概念模型設(shè)計(jì)即通常所說的需求分析，確定數(shù)據(jù)倉庫所需要訪問的信息，在需求分析階段確定操作數(shù)據(jù)、數(shù)據(jù)源及一些附加數(shù)據(jù)，建立較為穩(wěn)固的概念模型。由于數(shù)據(jù)倉庫的多維性，利用傳統(tǒng)的數(shù)據(jù)流程圖進(jìn)行需求分析已經(jīng)不能滿足需要。超立方體（hypercube）用超出三維的表示來描述一個對象，采用信息包圖的方法在平面上展開超立方體，用二維表格表示多維特征。信息包圖擁有 3 個重要對象，分別為指標(biāo)、維度和類別。指標(biāo)是在維度上衡量信息的一種方法，類別是為維度定義詳細(xì)的分類。利用信息包圖設(shè)計(jì)概念模型需要確定 3 大內(nèi)容：指標(biāo)、維度、層次類別。

2）邏輯模型設(shè)計(jì)。邏輯模型設(shè)計(jì)即設(shè)計(jì)星型圖，星型圖能夠清晰地反映概念模型中各個實(shí)體間的邏輯關(guān)系，并在此基礎(chǔ)上更好的組織檢索和查詢。其中，星型圖擁有指標(biāo)、維度和詳細(xì)類別等 3 個邏輯實(shí)體。指標(biāo)實(shí)體是位于星型圖中間的實(shí)體，對應(yīng)于概念模型中的指標(biāo)對象；維度實(shí)體是位于星型圖星角上的實(shí)體，對應(yīng)于概念模型的維度對象，作用是限制用戶的查詢結(jié)果，同時將主要指標(biāo)數(shù)據(jù)進(jìn)行聚和，從而縮小范圍。詳細(xì)類別實(shí)體對應(yīng)于概念模型中詳細(xì)類別對象，1 個維度內(nèi)的每個單元就是 1個類別，代表該維度內(nèi)的 1 個單獨(dú)層次。機(jī)電井主題星型模型如圖 1 所示。

3）物理模型設(shè)計(jì)。根據(jù)邏輯模型設(shè)計(jì)階段的星型圖，將指標(biāo)實(shí)體轉(zhuǎn)化為物理數(shù)據(jù)庫表，即事實(shí)表。事實(shí)表包括星型圖中心的指標(biāo)量和星型圖角上的維度實(shí)體中層次最低單位的主碼。維度實(shí)體通常也轉(zhuǎn)化為數(shù)據(jù)庫表，即維表，包括每一個維層次的主碼和對應(yīng)的值，維表的關(guān)鍵字是該維度實(shí)體對應(yīng)的詳細(xì)類別實(shí)體的主碼。維表和事實(shí)表通過維表關(guān)鍵字相關(guān)聯(lián)。

1.3 Map/Reduce

Google 公司提出的 Map/Reduce[7]是一種實(shí)現(xiàn)分布式計(jì)算任務(wù)的并行框架，是大數(shù)據(jù)并行計(jì)算的核心技術(shù)，它將海量數(shù)據(jù)處理任務(wù)劃分為 Map 和Reduce 過程。其中，Map 過程將原始的海量數(shù)據(jù)劃分為不同的數(shù)據(jù)子集，并根據(jù)用戶自定義的 Map 函數(shù)來對每一個數(shù)據(jù)子集進(jìn)行映射處理；Reduce 過程將 Map 過程處理后的結(jié)果根據(jù)用戶自定義的 Reduce函數(shù)進(jìn)行歸約處理。Map/Reduce 不僅隱藏了復(fù)雜的底層分布式計(jì)算實(shí)現(xiàn)的細(xì)節(jié)，而且給用戶提供了簡單、易用的功能接口及與性能相關(guān)的調(diào)優(yōu)參數(shù)，數(shù)據(jù)切割、任務(wù)調(diào)度、結(jié)點(diǎn)通信和系統(tǒng)容錯等功能均由 Map/Reduce 框架自動完成。

1.4 外殼片段立方體

在數(shù)據(jù)倉庫中，數(shù)據(jù)立方體可以用 Cube =（D，M）來表示。D ={D1，…，Dm} 是維度集合，其中m≥1，Di=（DHi，σ）表示一個維度屬性，DHi表示 D所有層次組成的一個有序集合，即h 代表 Di的層次數(shù)，是維度 D的第j 個層次，σ 是 DHi維層次上的依賴或偏序關(guān)系；M ={M1，…，Mn}是度量集合，其中 n≥1，Mi表示一個度量屬性。

為了便于論述，以水利普查數(shù)據(jù)中的機(jī)電井工程對象數(shù)據(jù)事實(shí)表為例，此事實(shí)表包括：行政區(qū)劃（addvcd）、所在地貌類型（dmlx）、機(jī)電井類型（jdjlx）和水源類型（sylx）4 個維度和供水井?dāng)?shù)量（sl）1 個度量，如表 2 所示。

表2 機(jī)電井工程事實(shí)表

行政區(qū)劃維分為?。╬rovince）、市（city）、縣（county）3 個層次，即 DHaddvcd= （nprovince，ncity，ncounty)。其中，province 的最大成員個數(shù) 32，city 的最大成員個數(shù) 21，county 的最大成員個數(shù) 31。

圖1 機(jī)電井主題星型模型

定義 1 外殼片段立方體 Shell Fragments Cube。對于一個 n 維的高維數(shù)據(jù)立方體 Cube（D，M），將維度屬性集合 D ={D1，…，Dn} 按照互不相交的原則，分割為 k 個獨(dú)立片段，物化這 k 個獨(dú)立的片段并創(chuàng)建倒排索引。對于 M ={M1，…，Mn} 度量屬性集合，創(chuàng)建 TID_measure 度量索引號對照表。

利用層次維編碼具有前綴層次語義特性，求得各個維相應(yīng)維層次屬性的編碼前綴及其 TID 關(guān)聯(lián)關(guān)系。表 2 中維度 addvcd 中層次 city 的編碼前綴及其TID 關(guān)聯(lián)關(guān)系如表 3 所示。

表3 維層次 city 的編碼前綴及其 TID 關(guān)聯(lián)表

2 外殼片段立方體并行計(jì)算與查詢

提出基于 Map/Reduce 計(jì)算框架的外殼片段立方體并行計(jì)算方法（Parallel Computation of Shell Fragments Cube，PSFC）。主要分為 Map 和 Reduce過程，具體描述如下：

2.1 并行計(jì)算算法

1）Map 過程。Map 過程接收數(shù)據(jù)子集，根據(jù)外殼片段劃分方法保存的 FID_dimensions 表，Map函數(shù)對數(shù)據(jù)進(jìn)行逐條處理，輸出映射處理后的 key/value 鍵值對。分為以下 3 種情況：

a. 對于層次維片段，生成各個維層次的編碼前綴 {PrefixB1，…，PrefixBh}，并處理成形式為＜ key =＜ FID，PrefixBi〉 ，value = TID 〉 的鍵值對，其中FID 代表片段編號，TID 代表行索引號。

b. 對于非層次維片段，每個片段采用 BUC 算法，從 ALL cuboids 向上深度優(yōu)先生成其它 cuboids，即計(jì)算出該片段的完全數(shù)據(jù)立方體。并處理成形式為 ＜ key = ＜ FID，tuplei 〉，value = TID 〉 的鍵值對，其中 tuplei 代表可能的數(shù)據(jù)單元。

c. 對于度量屬性，標(biāo)記其 key 的第 1 個屬性取值為 0，生成形式為 ＜ key = ＜ 0，TID 〉，value = measure 〉的鍵值對，其中 measure 代表度量取值。

Map 函數(shù)形式化描述如下：該并行計(jì)算方法在 Map 端的 shuffle 過程中，通過重新定義 Partition 函數(shù)的分發(fā)規(guī)則：將 Map 過程輸出的所有鍵值對中，具有相同片段編號的 key/value 鍵值對分發(fā)到同一個 Reducer 上進(jìn)行處理。

2）Reduce 過程。Reduce 過程接收 Shuffle 過程處理得到的屬于同一組的數(shù)據(jù)集，交給自定義的Reduce 函數(shù)進(jìn)行處理，由于同一個 Reducer 處理的鍵值對中 FID 取值相同，那么每個 Reducer 處理結(jié)果即為 1 個外殼片段或 TID_measure 表。數(shù)據(jù)處理分以下 3 種情況：

a. 對于層次維，將 key 值中 PrefixBi相同的鍵值對進(jìn)行合并，其中 value 值求并集，處理輸出形式為＜ key = PrefixBi，value = ＜ TID1，…，TIDj〉〉。

b. 對于非層次維，將 key 值中非層次維聚集單元相同的鍵值對進(jìn)行合并，其中 value 值求并集，輸出形式為 ＜ key = tuplei，value = ＜ TID1，…，TIDj〉〉。

c. 對于度量，即 key 值中第 1 個屬性為 0 的鍵值對，處理輸出形式為 ＜key= TID，value = measure〉。

輸入。Shuffle 過程輸出；

輸出。所有外殼片段及其倒排索引，以及度量索引表（TID_measure 表）。

2.2 并行查詢算法

并行查詢算法也主要分為 2 個階段：Map 和Reduce 過程。若查詢條件中包含層次維，將其預(yù)計(jì)算為層次維編碼或編碼前綴。

1）Map 過程。遍歷外殼片段立方體所有的鍵值對，查找出符合查詢條件的鍵值對并輸出；自定義Map 函數(shù)中定義 1 個全局變量 flag，以此減少 Map函數(shù)處理鍵值對數(shù)量，提高查詢性能。

2）Reduce 過程。對 Map 過程處理所得的鍵值對，取其 value 值進(jìn)行求交集運(yùn)算，得到符合查詢條件的索引號集合 QList。在 TID_measure 中取出QList 對應(yīng)的度量值，根據(jù)給定的聚集函數(shù)，計(jì)算出用戶所需的聚集結(jié)果。

并行查詢輸入輸出如下：

5 根據(jù)給定聚集函數(shù)，聚集計(jì)算 QList 對應(yīng)的度量值；

2.3 算法性能測試

本實(shí)驗(yàn)用到的 Hadoop 集群環(huán)境由 6 臺機(jī)器組成，實(shí)現(xiàn)語言為 Java，平臺為 Eclipse。采用水利普查機(jī)電井對象脫密數(shù)據(jù)，包含 10 個維度和 5 個度量，在實(shí)驗(yàn)前已對各字段都進(jìn)行了規(guī)范化處理。實(shí)驗(yàn)對外殼片段立方體傳統(tǒng)方法和 PSFC 方法在數(shù)據(jù)量由（1～5）×106條構(gòu)造時間進(jìn)行比較。如圖 2 所示。

圖2 不同數(shù)據(jù)量 PSFC 與傳統(tǒng)方法構(gòu)造時間比較

由圖 2 可以看出，當(dāng)數(shù)據(jù)量較少時，由于集群需要額外的通訊和數(shù)據(jù)傳送等開銷，PSFC 方法的優(yōu)勢不太明顯，構(gòu)造時間大約是傳統(tǒng)方法的 2/3；但隨著數(shù)據(jù)量的不斷增大，PSFC 方法的優(yōu)勢會越來越明顯，到 5×106條數(shù)據(jù)時，構(gòu)造時間小于傳統(tǒng)方法的1/4。綜上所述，PSFC 方法在計(jì)算高維、數(shù)據(jù)量大的數(shù)據(jù)立方體時有顯著的優(yōu)勢，可支持水利普查多維度、大數(shù)據(jù)量的數(shù)據(jù)立方體計(jì)算。

3 水利普查成果數(shù)據(jù)多維分析系統(tǒng)

首先，采用 PSFC 算法計(jì)算出水利普查成果數(shù)據(jù)的各個外殼片段立方體；然后，利用開發(fā)工具Eclipse，采用 Java，JSP，Groovy，F(xiàn)usionCharts 等技術(shù)，使用預(yù)計(jì)算的外殼片段立方體數(shù)據(jù)，搭建水利普查成果數(shù)據(jù)多維分析系統(tǒng)。分析系統(tǒng)頁面至左向右分為 3 個部分，第 1 部分根據(jù)需要逐級選取所需分析的主題，第 2 部分選擇相應(yīng)的分析維度，第3 部分以表格、柱狀圖或圖形的方式展現(xiàn)水利普查成果數(shù)據(jù)分析結(jié)果。

分析系統(tǒng)可提供切片、切塊、旋轉(zhuǎn)、上卷、下鉆等 OLAP 操作，對于有層次結(jié)構(gòu)的維度，點(diǎn)擊相應(yīng)維度實(shí)現(xiàn)鉆取下一層次的數(shù)據(jù)，具體實(shí)現(xiàn)如圖 3所示。如柱狀圖顯示的是全國各省所有機(jī)電井工程2011年取水量，點(diǎn)擊某省可獲取該省各市機(jī)電井工程 2011年取水量，如果繼續(xù)點(diǎn)擊某市，可獲得該市下各個區(qū)的機(jī)電井工程 2011年取水量。

4 結(jié)語

外殼片段立方體并行計(jì)算和查詢方法，相對于串行外殼片段立方體，在高維、數(shù)據(jù)量大時有顯著的優(yōu)勢，可支持水利普查多維度、大數(shù)據(jù)量的數(shù)據(jù)立方體計(jì)算與查詢。將計(jì)算出的外殼片段立方體應(yīng)用于系統(tǒng)展示，清晰簡潔直觀地展現(xiàn)水利普查成果數(shù)據(jù)，向用戶提供及時分析數(shù)據(jù)以輔助決策。當(dāng)然，本方法還有很多需要研究和改進(jìn)的地方，比如增量更新維護(hù)方面的性能表現(xiàn)，以及如何進(jìn)一步加快查詢響應(yīng)時間等方向，都值得繼續(xù)研究。

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

[2] Gray J, Chaudhuri S, Bosworth A, et al. Data cube: A Relational Aggregation Operator Generalizing Group-by, Crosstab, and Sub-totals[J]. Data Mining and Knowledge Discovery, 1997, 1 (1): 29-53.

[3] Jiang F M, Pei J, Fu A W. Ix-cubes: Iceberg Cubes for Data Warehousing and Olap on Xml Data[C]//Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management. New York: ACM, 2007: 905-908.

[4] Wang Z, Xu Y. Minimal Condensed Cube: Data Organization, Fast Computation, and Incremental Update[C]//Internet Computing in Science and Engineering, Harbin: International Conference on. IEEE, 2008: 60-67.

[5] Li C, Cong G, Tung A K H, et al. Incremental Maintenance of Quotient Cube for Median[C]//Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington: ACM, 2004: 226-235.

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

[7] Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters[J]. Communications of the ACM, 2008, 51 (1): 107-113.

[8] Li X, Han J, Gonzalez H. High-dimensional OLAP: A Minimal Cubing Approach[C]//Proceedings of the Thirtieth International Conference on Very Large Data Bases-Volume 30. Urbana: VLDB Endowment, 2004: 528-539.

[9] You J G, Xi J Q, Zhang P J, et al. A Parallel Algorithm for Closed Cube Computation[C]//Proceedings of the 7th IEEE/ACIS International Conference on Computer and Information Science (ACIS-ICIS), Portland, Oregon, USA, 2008. Washington: IEEE Computer Society, 2008: 95-99.

Research on Water Census Data Cube Parallel Computing Method

TANG Shanshan, WAN Dingsheng, ZHU Yuelong, YU Yufeng, ZHU Kai

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

Water census data has the following characteristics: large amount of data, many dimensions and dimension hierarchy, etc. Chemical water census data cube, the time and space cost is very high. This paper puts forward a new method of parallel computing for shell fragments cube based on Map/Reduce calculation model. The experimental results indicate that the method can effectively improve the computation efficiency of shell fragments cube on large data sets, decrease the cost of the time and space of water census data cube. Water census data cube is applied to multidimensional analysis system. It clearly and intuitively shows water census data from several aspects.

water census; data cube; shell fragments cube; technology of Map/Reduce

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

TV21

A

1674-9405(2015)04-0001-07

2015-03-25

水利部公益性行業(yè)科研專項(xiàng)經(jīng)費(fèi)項(xiàng)目（201501022）

唐珊珊（1993－），女，四川廣安人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與知識發(fā)現(xiàn)。