唐珊珊，朱躍龍，朱凱

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

◎數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎

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

唐珊珊，朱躍龍，朱凱

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

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

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

1　引言

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

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

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

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

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

表1　水庫(kù)工程事實(shí)表

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

2.1外殼片段立方體

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

2.2層次維編碼

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

定義2（層次維編碼）［8-10］層次維Di的層次維編碼，是維度Di中所有層次屬性采用混合索引（B-tree和bit code）技術(shù)進(jìn)行二進(jìn)制編碼，按層次由高到低，依次組合而成的混合編碼。每層編碼位數(shù)為，其中mj為層最大成員個(gè)數(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維成員的層編碼前綴，由位掩碼與層次維編碼按位與操作計(jì)算得到，即。

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

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

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

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

3　外殼片段立方體并行計(jì)算與查詢(xún)

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

圖1　Map過(guò)程實(shí)例圖

3.1并行計(jì)算方法

（1）Map過(guò)程

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

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

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

③對(duì)于度量，標(biāo)記其key的第一個(gè)屬性取值為0，生成形式為＜key=＜0，TID＞，value=measure＞的鍵值對(duì)，其中measure代表度量取值。Map過(guò)程示例圖如圖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過(guò)程包含在Map和Reduce兩端中，本文算法在Map端的shuffle過(guò)程中，通過(guò)重新定義Partition函數(shù)［16］的分發(fā)規(guī)則：將Map過(guò)程輸出的所有鍵值對(duì)中具有相同片段編號(hào)（FID）的key/value鍵值對(duì)，分發(fā)到相同的組中，最終將同一組的數(shù)據(jù)傳送到相同的Reduce節(jié)點(diǎn)上進(jìn)行處理。

（2）Reduce過(guò)程

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

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

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

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

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

輸入：shuffle過(guò)程輸出；

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

圖2　Reduce過(guò)程實(shí)例圖

3.2并行查詢(xún)方法

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

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

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

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

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

4　性能分析

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

表4　實(shí)驗(yàn)所用集群的配置

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

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

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

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

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

5　結(jié)語(yǔ)

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

［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］朱凱，萬(wàn)定生，程習(xí)鋒.水利普查成果分析中數(shù)據(jù)立方體計(jì)算研究［J］.計(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ù)倉(cāng)庫(kù)系統(tǒng)中一種高效的多維層次聚集算法［J］.計(jì)算機(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)，趙航，張陽(yáng)，等.基于Map/Reduce的海量數(shù)據(jù)挖掘技術(shù)研究［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（20）：112-117.

［14］師金鋼，鮑玉斌，冷芳玲，等.MapReduce環(huán)境下的并行Dwarf立方構(gòu)建［J］.計(jì)算機(jī)科學(xué)與探索，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實(shí)戰(zhàn)［M］.2版.北京：機(jī)械工業(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è)科研專(zhuān)項(xiàng)（No.201501022）。

唐珊珊（1993—），女，碩士研究生，主要研究方向：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)；朱躍龍（1959—），男，教授，CCF會(huì)員，主要研究方向：數(shù)據(jù)挖掘與知識(shí)發(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)絡(luò)優(yōu)先出版：2015-07-24，http://www.cnki.net/kcms/detail/11.2127.TP.20150724.1549.002.html