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

唐珊珊，朱躍龍，朱凱

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

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機器學習◎

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

唐珊珊，朱躍龍，朱凱

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

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

聯(lián)機分析處理；外殼片段立方體；Map/Reduce技術(shù)；并行計算

1　引言

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

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

2　數(shù)據(jù)立方體

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

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

表1　水庫工程事實表

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

2.1外殼片段立方體

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

2.2層次維編碼

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

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

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

表2　addvcd層次維編碼

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

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

利用層次維編碼具有前綴層次語義特性，求得各維相應維層次屬性的編碼前綴及其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.3外殼片段分段方法

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

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

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

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

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

圖1　Map過程實例圖

3.1并行計算方法

（1）Map過程

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

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

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

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

Map函數(shù)形式化描述如下：

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

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

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

（2）Reduce過程

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

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

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

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

Reduce函數(shù)形式化描述如下：

輸入：shuffle過程輸出；

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

圖2　Reduce過程實例圖

3.2并行查詢方法

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

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

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

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

輸出：查詢結(jié)果。

4　性能分析

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

表4　實驗所用集群的配置

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

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

圖3　不同數(shù)據(jù)量構(gòu)造時間比較

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

圖4　集群節(jié)點數(shù)量影響

5　結(jié)語

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

［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，F(xiàn)u 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］朱凱，萬定生，程習鋒.水利普查成果分析中數(shù)據(jù)立方體計算研究［J］.計算機與數(shù)字工程，2014，42（9）：1591-1594.

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

［9］胡孔法，陳崚，顧頎，等.數(shù)據(jù)倉庫系統(tǒng)中一種高效的多維層次聚集算法［J］.計算機集成制造系統(tǒng)，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］李偉衛(wèi)，趙航，張陽，等.基于Map/Reduce的海量數(shù)據(jù)挖掘技術(shù)研究［J］.計算機工程與應用，2013，49（20）：112-117.

［14］師金鋼，鮑玉斌，冷芳玲，等.MapReduce環(huán)境下的并行Dwarf立方構(gòu)建［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實戰(zhàn)［M］.2版.北京：機械工業(yè)出版社，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

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

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

2015-02-03

2015-04-22

1002-8331（2015）22-0124-06

CNKI網(wǎng)絡優(yōu)先出版：2015-07-24，http://www.cnki.net/kcms/detail/11.2127.TP.20150724.1549.002.html