基于Map/Reduce的外殼片段立方體并行計算方法

唐珊珊，朱躍龍，朱凱

河海大學計算機與信息學院，南京210098

◎數據庫、數據挖掘、機器學習◎

基于Map/Reduce的外殼片段立方體并行計算方法

唐珊珊，朱躍龍，朱凱

河海大學計算機與信息學院，南京210098

針對高維、維度分層的大數據集，提出一種基于Map/Reduce框架的并行外殼片段立方體構建算法。算法采用Map/Reduce框架，實現外殼片段立方體的并行構建與查詢。構建算法在Map過程中，計算出各個數據分塊所有可能的數據單元或層次維編碼前綴；在Reduce過程中，聚合計算得到最終的外殼片段和度量索引表。實驗證明，并行外殼片段立方體算法一方面結合了Map/Reduce框架的并行性和高擴展性，另一方面結合了外殼片段立方體的壓縮策略和倒排索引機制，能夠有效避免高維數據物化時數據量的爆炸式增長，提供快速構建和查詢操作。

聯機分析處理；外殼片段立方體；Map/Reduce技術；并行計算

1　引言

數據立方體（Data Cube）［1］物化能夠提高OLAP的性能，但完全物化通常需要很高的時空成本。為提高數據立方體生成和查詢效率，許多專家學者提出Iceberg Cube［2］、Condensed Cube［3］和Quotient Cube［4］等數據立方體物化方法，這些方法在多維分析應用中起著重要的作用。物化高維數據集時，數據立方體體積將隨著維度個數的增加呈指數級增長，導致十分昂貴的物化代價。采用上述物化方法，只能延遲這種數據量爆炸，不能從根本上解決問題。文獻［5］提出外殼片段立方體的概念，有效避免高維數據立方體體積爆炸式增長。然而，在數據量非常龐大的情況下，計算外殼片段立方體時間成本仍然很高，并行計算是行之有效的解決辦法。Google公司提出的Map/Reduce［6］是一種實現分布式計算任務的并行框架，它將海量數據處理任務劃分為Map過程和Reduce過程，用戶只需考慮如何自定義Map函數和Reduce函數以滿足業務需求，而不需要考慮復雜的底層分布式計算實現細節。

水利普查成果數據具有覆蓋面廣、數據量大、維度多、維度分層等特點，數據維度可以達到20個，記錄數也常常超過106條，物化水利普查成果數據立方體需要很高的時空成本［7］。本文提出一種基于Map/Reduce框架的外殼片段立方體并行計算方法，提高水利普查成果數據立方體構造與查詢的效率。

2　數據立方體

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

為了便于本文論述，以水利普查成果數據中水庫工程對象數據事實表為例，此事實表包括：行政區劃（addvcd）、工程規模（gcgm）、水庫類型（sklx）和建設情況（jsqk）四個維度和總庫容（zkr）一個度量，如表1所示。

表1　水庫工程事實表

其中行政區劃維addvcd分為?。╬rovince）、市（city）、縣（county）三個層次，即DHaddvcd=（province，city，county）。其中，province的最大成員個數為32，city的最大成員個數為21，county的最大成員個數為31。

2.1外殼片段立方體

定義1（外殼片段立方體Shell Fragments Cube）對于一個n維的高維數據立方體Cube（D，M），將維度集合D=｛D1，D2，…，Dn｝按照互不相交的原則，分割為k個獨立片段，物化這k個獨立的片段并創建倒排索引。對于M=｛M1，M2，…，Mn｝度量集合，創建度量索引號對照表（TID_measure表）。

2.2層次維編碼

水利普查成果數據中存在3個核心的層次維（行政區劃、水資源區劃和流域水系），對水利普查成果數據分析有著舉足輕重的作用，為保持層次維上的偏序依賴關系，提高OLAP查詢效率，引入壓縮性能強且具有層次語義特性的層次維編碼，代替原表中關鍵字［8-10］。

定義2（層次維編碼）［8-10］層次維Di的層次維編碼，是維度Di中所有層次屬性采用混合索引（B-tree和bit code）技術進行二進制編碼，按層次由高到低，依次組合而成的混合編碼。每層編碼位數為，其中mj為層最大成員個數。

例1：層次維addvcd中層次province編碼位數為，層次city編碼位數為，層次county編碼位數為，那么Baddvcd位數為5+5+5=15， addvcd層次維編碼如表2所示。

表2　addvcd層次維編碼

定義3（位掩碼）［9］維層次的位掩碼表示維度Di的層及其祖先層次位編碼值為1，其子孫層次位編碼值為0的混合編碼。

定義4（編碼前綴）維度Di維成員的層編碼前綴，由位掩碼與層次維編碼按位與操作計算得到，即。

利用層次維編碼具有前綴層次語義特性，求得各維相應維層次屬性的編碼前綴及其TID關聯關系。表2中維度addvcd中層次city的編碼前綴及其TID關聯關系如表3所示。

表3　維層次city的編碼前綴及其TID關聯表

2.3外殼片段分段方法

外殼片段立方體需將維度集合D=｛D1，D2，…，Dn｝劃分為k個互不相交的維片段，依次對維片段編號FID，并保存FID與維度對照表FID_dimensions。對于具有層次維的數據集，片段劃分存在兩種情況：

（1）非層次維，根據查詢需求，將頻繁查詢的維度或者需一起查詢的維度定制到同一個維片段中，維片段大小為f（其中2≤f≤4）［10］，聚集cuboids形式如：｛［Di，Di+1，Di+2］，…，［Dn-2，Dn-1，Dn］｝，對于每個維片段，計算其數據立方體并創建倒排索引。

（2）層次維，計算層次維編碼，根據位掩碼計算出該維度各層次的編碼前綴，聚集cuboids的形式：｛［PrefixB1（Di），PrefixB2（Di），…，PrefixBh（Di）］，…，［PrefixB1（Dj），PrefixB2（Dj），…，PrefixBh（Dj）］｝，對每個片段創建倒排索引。一個層次維的聚集cuboids已經較為復雜，因此設為一個單獨的維片段。

3　外殼片段立方體并行計算與查詢

Map/Reduce是大數據并行計算的核心技術，給用戶提供了簡單、易用的功能接口以及與性能相關的調優參數。其中，Map過程將原始的海量數據劃分為不同的數據子集，并根據用戶自定義的Map函數對每一個數據子集進行映射處理；Reduce過程將Map過程處理后的結果根據用戶自定義的Reduce函數進行歸約處理［11-13］。本文提出基于Map/Reduce框架的外殼片段立方體并行計算方法（Parallel computation of Shell Fragments Cube，PSFC），算法主要分為Map和Reduce兩個過程［14-15］，使用水利普查機電井對象脫密數據，維片段劃分：層次維作為單獨的維片段，非層次維劃分為大小為3的維片段，具體描述如下：

圖1　Map過程實例圖

3.1并行計算方法

（1）Map過程

Map過程首先將原始的海量數據劃分為不同的數據子集，然后自定義Map函數根據片段編號維度對照表（FID_dimensions表），對數據進行逐條處理，輸出映射處理后的key/value鍵值對［16］。對每條數據處理分為以下三種情況：

①對于層次維，根據編碼前綴定義計算出該維各層次的編碼前綴｛PrefixB1，PrefixB2，…，PrefixBh｝，并映射成形式為＜key=＜FID，PrefixBi＞，value=TID＞的鍵值對，其中FID代表片段編號，TID代表行索引號。

②對于非層次維，根據FID_dimensions表，將屬于同一個維片段的維數據片段采用BUC算法，自底向上深度優先生成其所有可能的數據元組，即計算出該數據片段的完全數據立方體。并處理成形式為＜key=＜FID，tuplei＞，value=TID＞的鍵值對，其中tuplei代表可能的數據單元；

③對于度量，標記其key的第一個屬性取值為0，生成形式為＜key=＜0，TID＞，value=measure＞的鍵值對，其中measure代表度量取值。Map過程示例圖如圖1所示。

Map函數形式化描述如下：

輸入：＜key=TID，value=C＞，其中C代表一條原始數據；

輸出：①層次維度：＜key=＜FID，PrefixBi＞，value= TID＞；②非層次維度：＜key=＜FID，tuplei＞，value= TID＞；③度量：＜key=＜0，TID＞，value=measure＞。

shuffle過程包含在Map和Reduce兩端中，本文算法在Map端的shuffle過程中，通過重新定義Partition函數［16］的分發規則：將Map過程輸出的所有鍵值對中具有相同片段編號（FID）的key/value鍵值對，分發到相同的組中，最終將同一組的數據傳送到相同的Reduce節點上進行處理。

（2）Reduce過程

Reduce過程接收shuffle過程處理得到的屬于同一組的數據集，交給自定義的Reduce函數進行處理，由于同一個Reduce處理的鍵值對中FID的取值相同，那么每個Reduce的處理結果即為一個外殼片段或TID_measure表。數據處理分為以下三種情況：

①對于層次維，將key值中PrefixBi相同的鍵值對進行合并，其中value值求并集，處理輸出形式為：＜key= PrefixBi，value=＜TID1，TID2，…，TIDj＞＞。該Reduce過程處理結束，即得到一個層次維片段及其倒排索引。

②對于非層次維，將key值中非層次維聚集單元相同的鍵值對進行合并，其中value值求并集，輸出形式為：＜key=tuplei，value=＜TID1，TID2，…，TIDj＞＞。該Reduce過程處理結束，即得到一個非層次維片段及其倒排索引。

③對于度量，即key值中第一個屬性為0的鍵值對，處理輸出形式為：＜key=TID，value=measure＞。該Reduce過程處理結束，即得到該外殼片段立方體的TID_measure表。Reduce過程示例圖如圖2所示。

Reduce函數形式化描述如下：

輸入：shuffle過程輸出；

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

圖2　Reduce過程實例圖

3.2并行查詢方法

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

Map過程，遍歷外殼片段立方體所有的鍵值對，查找出符合查詢條件的鍵值對并輸出；自定義Map函數中定義一個全局變量flag，（取值為1表明該片段包含所需維度，則遍歷該片段；取值為0表明該片段不包含所需維度，則忽略該片段），以此減少Map函數處理鍵值對數量，提高查詢性能。

Reduce過程，對Map過程處理所得的鍵值對，取其value值進行求交集運算，得到符合查詢條件的索引號集合QList。在TID_measure中取出QList對應的度量值，根據給定的聚集函數（本文定義聚集函數為求和sum），計算出用戶所需的聚集結果。

輸入：①已預計算的外殼片段集合｛fragment1，fragment2，…，fragmentk｝；②TID_measure表；③＜d1，d2，…，dn，M＞形式的查詢條件。

輸出：查詢結果。

4　性能分析

實驗一比較傳統外殼片段立方體與本文的PSFC方法構造性能，實驗二比較集群節點數量對PSFC方法和并行查詢算法的影響，并對實驗結果進行分析。實驗Hadoop集群環境由6臺機器組成，包含1個主控節點Master和5個從屬節點Slave，它們通過路由器互連。6臺節點硬件配置相同（CPU/內存/存儲空間：雙核2.5 GHz/1 GHz/10 GHz）。搭載的操作系統均為Ubuntu 14.10，Hadoop版本號是0.20.203.0，基于jdk1.7.0_15搭建。實現語言為java，平臺eclipse，集群基本信息和網絡配置情況如表4所示。

表4　實驗所用集群的配置

實驗采用水利普查機電井對象脫密數據，有10個維度屬性（行政區劃、流域水系、水資源區劃、流域片、機電井類型、井壁管材料、應用狀況、所在地貌類型、水源類型、主要取水用途）和5個度量屬性（實際灌溉面積、供水井數量、取水量、實際供水人口、人均取水量），數據量為5×106條，實驗前已對各字段都進行規范化處理。

實驗一對傳統外殼片段立方體方法和PSFC方法構造時間進行比較，圖3中shell fragment cube曲線表示傳統外殼片段立方體方法，PSFC曲線表示本文PSFC方法，實驗運行在節點數為6的集群上，維度數目為10，比較數據量由1×106到5×106條的情況。由圖3可以看出，當數據量較少時，PSFC方法的優勢不太明顯，構造時間大約是傳統方法的2/3，這是由于集群需要額外的通訊和數據傳送等開銷。隨著數據量的不斷增大，PSFC方法的優勢越來越明顯，到5×106條數據時，構造時間小于傳統方法的1/4。并且隨著數據量的上升，傳統方法的構造時間上升較快，而PSFC方法的構造時間緩慢升高。這是因為隨著數據量的提高，集群開銷遠小于構造時間，并行優勢和算法改進得到體現。

圖3　不同數據量構造時間比較

實驗二比較集群節點數對并行構造PSFC方法和查詢算法的影響，實驗數據維度數目為10，數據量為1×106條，集群節點數量由3增加到6。圖中Construction代表并行構造曲線，Search曲線代表并行查詢曲線。實驗結果如圖4所示，隨著集群節點數量的增加，構造時間接近于線性減少，而查詢時間變化較小。原因在于外殼片段的構造相對費時，集群節點的增加會帶來較大的收益，而查詢的大部分時間被花費在節點之間的通訊和協調代價上。綜上，PSFC方法具有良好的可擴展性，根據具體應用環境中數據量的不同，系統可以通過調整集群節點數量，有效地調整并行外殼立方體構造的效率。

圖4　集群節點數量影響

5　結語

文中提出基于Map/Reduce框架的外殼片段立方體并行計算方法和并行查詢方法。性能分析表明，相對于串行外殼片段立方體，并行計算方法的性能在高維、數據量大時有顯著的優勢，可支持水利普查維度多、數據量大的數據立方體計算與查詢。當然，本文方法還有很多需要研究和改進的地方，比如在Map/Reduce計算時的調度優化，增量更新維護方面的性能表現，以及如何進一步加快查詢響應時間等，都是值得研究的方向。

［1］Gray J，Chaudhuri S，Bosworth A，et al.Data cube：A relational aggregation operator generalizing group-by，cross-tab，and sub-totals［J］.Data Mining and Knowledge Discovery，1997，1（1）：29-53.

［2］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.ACM，2007：905-908.

［3］Wang Z，Xu Y.Minimal condensed cube：data organization，fast computation，and incremental update［C］//International Conference on Internet Computing in Science and Engineering.IEEE，2008：60-67.

［4］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.ACM，2004：226-235.

［5］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，VLDB Endowment，2004：528-539.

［6］Dean J，Ghemawat S.Map/Reduce：simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107-113.

［7］朱凱，萬定生，程習鋒.水利普查成果分析中數據立方體計算研究［J］.計算機與數字工程，2014，42（9）：1591-1594.

［8］Markl V，Ramsak F，Bayer R.Improving OLAP performancebymultidimensionalhierarchicalclustering［C］// Proc of IDEAS’99，1999：165-177.

［9］胡孔法，陳崚，顧頎，等.數據倉庫系統中一種高效的多維層次聚集算法［J］.計算機集成制造系統，2007，13（1）：196-201.

［10］Stockinger K.Bitmap indices for speeding up high-dimensional data analysis［M］//Database and Expert Systems Applications.Berlin Heidelberg：Springer，2002：881-890.

［11］Chen Y，Dehne F，Eavis T，et al.Parallel ROLAP Data Cube Construction on Shared-Nothing Multiprocessors［J］. Distributed and Parallel Databases，2004，15（3）.

［12］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，DC，USA：IEEEComputerSociety，2008：95-99.

［13］李偉衛，趙航，張陽，等.基于Map/Reduce的海量數據挖掘技術研究［J］.計算機工程與應用，2013，49（20）：112-117.

［14］師金鋼，鮑玉斌，冷芳玲，等.MapReduce環境下的并行Dwarf立方構建［J］.計算機科學與探索，2011，5（5）：398-409. DOI：10.3778/j.issn.1673-9418.2011.05.002.

［15］Sergey K，Yury K.Applying Map-reduce paradigm for parallel closed cube computation［C］//2009 First International Conference on Advances in Databases，Knowledge，and Data Applications.IEEE Computer Society，2009：62-67.

［16］陸嘉恒.Hadoop實戰［M］.2版.北京：機械工業出版社，2012：2-3.

Parallel computation of shell fragments cube Map/Reduce-based.

TANG Shanshan，ZHU Yuelong，ZHU Kai

College of Computer and Information，Hohai University，Nanjing 210098，China

In the high-dimensional and dimension hierarchical big data materializing，this paper proposes an efficient parallel shell fragments cube construction algorithm using Map/Reduce framework.The algorithm achieves parallel building and querying of shell fragments cube.For each data partition，map process of the construction algorithm calculates all possible data unit or prefixB encoding；Reduce process aggregates to calculate the ultimate shell fragments and measure index table.Experiments show that the parallel shell fragments cube algorithm not only combines the parallelism and scalability of Map/Reduce framework，but also combines the compression strategy and inverted index structure of shell fragments cube.The parallel shell fragments cube algorithm can effectively avoid the explosion of data volumes while materializing high-dimensional data，and provides the quick build and query operations.

On-Line Analysis Processing（OLAP）；shell fragments cube；Map/Reduce；parallel computation

A

TP391

10.3778/j.issn.1002-8331.1502-0051

水利部公益性行業科研專項（No.201501022）。

唐珊珊（1993—），女，碩士研究生，主要研究方向：數據挖掘與知識發現；朱躍龍（1959—），男，教授，CCF會員，主要研究方向：數據挖掘與知識發現；朱凱（1990—），男，碩士研究生，主要研究方向：數據挖掘與信息系統。E-mail：tangshanshanz@126.com

2015-02-03

2015-04-22

1002-8331（2015）22-0124-06

CNKI網絡優先出版：2015-07-24，http://www.cnki.net/kcms/detail/11.2127.TP.20150724.1549.002.html