基于MapReduce的数据立方体分区优化算法研究

张子浪+++葛昂+++郑家民

【 摘 要 】 文章利用并行计算框架MapReduce，探索数据立方体的计算问题。数据立方体的计算存在两个关键问题，一个是计算时间的问题，另一个是立方体的体积问题。随着维度的增加，计算时间将呈现指数级的增长，立方体的体积也是如此。尽管MapReduce是一个优秀的并行计算框架，但在处理数据倾斜时，分区算法不够完善，导致一些计算任务时间过长，影响整个作业的完成时间。本文通过数据采样的方式，优化数据分区，实验结果表明，数据立方体的计算的性能明显提升。为解决数据立方体体积过大的问题，在Reduce阶段将最终的结果输出到基于NoSQL的HBase数据库进行存储，HBase方便水平扩展，同时也便于日后对数据立方体的查询。

【 关键词 】 数据立方体；数据分区；数据分析

【 文献标识码 】 A

1 引言

在互联网和电子商务领域，一些运营商以及电子商务平台提供商拥有大量的用户，并以云计算的方式向用户提供服务，这些服务响应用户的请求，在后端产生相应的数据，由于数据的集中储存以及用户的频繁请求，使得数据量呈现快速增长。在电子政务领域，一些政府部门根据自身信息化的发展水平及业务发展的需要，将信息化系统集中部署到省级机构，各地、市通过专网访问。这其中信息化化建设步伐更快的政府部门，在省级集中的基础上，实行全国数据的集中。在科学试验领域，科学家所观测的对象也产生了大量的数据，比如天文学当中利用天文望远镜，只需几天的时间，并能扫描半个天空。

就这些领域的数据产生速度而言，一些IT系统每天产生TB级的数据量，有的则多达PB级。有了大量的数据，就会产生数据挖掘的需求，包括对数据进行汇总分析。数据立方体能够很好地表达多维的结构化数据的汇总分析，传统的联机分析（OLAP）技术对于立方体的计算方法也相对较为成熟。传统的OLAP根据数据储存方式的不同，可分为两类：一类是ROLAP，以关系表进行多维数据的表示和存储；另一类是MOLAP，以多维数组进行多维数据的表示和存储。ROLAP计算数据立方体就是利用SQL中的group by语句对特定维度属性集合的所有子集分别集合，后来引入了Cube操作，一个Cube等价于多个Group by。MOLAP计算数据立方体时基于数组对数据进行集合，一种比较成熟的算法是多路数据聚集算法。

尽管基于传统的数据立方体的并行计算的算法比较成熟，但其不能直接应用于大数据的计算，因为由于这些大数据基于文件系统存储，而不是基于关系型数据库存储或者数组，而且，其数据量也大得多。

针对大数据的分析，Google提出了map-reduce的并行计算框架，结合上千台的廉价PC服务器，使得大数据的分析能够在很短时间之内完成，Hadoop是基于该编程模型的开源实现。 利用Hadoop进行数据立方体进行计算的研究相对较少，有的利用Hadoop计算数据立方体，但没有考虑数据的优化分区，直接采用Hadoop缺省的分区方式，这种方式存在缺陷，不能让高度倾斜的数据（少数几个键值出现的次数占据了非常大的比例）均匀分配给各个并行的计算任务，导致某些计算任务的输入数据过多，从而导致其完成时间滞后于其它计算任务，影响整个作业的完成时间。

本文给出了基于Map-Reduce计算数据立方体的算法以及分区优化算法，为让数据均匀分布到各个Reduce任务，采用数据抽样的方式决定采用何种分区方式，为并行计算立方体提供了一种新方式。

数据立方体有多种，完整数据立方体，冰山立方体，封闭立方体。冰山立方体和封闭立方体考虑了数据立方体的体积，减少不必要的存储。由于封闭立方体或者冰山立方体中的某一个子立方体很可能就是一个完整的立方体，因此，计算完整立方体的过程不可避免，而且，完整立方体也是其它立方体的基础。所以本文研究完整立方体的计算。

在此先介绍并行计算、数据立方体、Hadoop的相关概念，给出通用的计算数据立方体的Hadoop实现，在分析可能由于数据分布不平衡而导致的计算不平衡的基础上，设计基于抽样的分区算法。然后结合实验对算法进行分析。最后对当前工作进行总结，并提出未来的可能研究方向。

2 概念

2.1 数据立方体

实体关系模型主要应用于在关系型数据库中，这样的二维数据模型比较适合事务处理，但是不适合数据的在线分析。在数据仓库当中，往往需要从多个角度对数据进行分析，因此需要多维的数据模型，数据立方体就是用来描述多维数据模型的。

给定基本关系R（A1，A2，A3，…，An，M），由R产生的数据立方体是R的属性的所有的可能组合，n个属性产生2n个组合。A1，A2，A3，…，An为立方体的属性维，M为度量维，M是一个数字函数，描述数据以何种方式进行聚合或者计算。

取n=3，即基本关系R（A1，A2，A3，M）产生的立方体由以下分组构成：

{（A1，A2，A3），（A1，A2），（A1，A3），（A2，A3），（A1），（A2），（A3），（）}。

度量维常见的聚合函数有SUM，MAX，MIN，AVG等。聚合函数可分为三类，分别是分布式，代数式，综合式的。考虑对分组P中的元素进行聚合。

分布式的聚合函数：，Pi（i=1，2，3，…n）为P的两两不相交的子集，即∪Pni=1=P并且□ij，i≠j，Pi∩Pj=?，如果存在函数G，使得F（P）=G（F（P1）， F（P2）， …，F（Pn）），那么称聚合函数F为分布式式函数。COUNT（）， MIN（）， MAX（），SUM（）都是分布式函数。除了COUNT函数外，其余三个几个函数F=G。对于COUNT函数而言，G=SUM，即COUNT（P）=SUM（COUNT（P1）， COUNT（P2）， COUNT（P3），…， COUNT（Pn））。endprint

代数式聚合函数：Pi（i=1，2，3，…n）为P的两两不相交的子集，∪Pni=1=P并且□ij，i≠j，Pi∩Pj=?，如果存在函数G和函数H（对于所有的Pi，H函数返回一个k元组），使得F（P）=G（H （P1）， H（P2）， …，H （Pn）），那么称聚合函数F为分布式式函数。AVG函数就是代数式函数，对每个每个Pi，H函数返回一个二元组（sumi，counti），G函数对所有的sumi及counti分别相加，然后相除产生整体的平均值，即 。

整体式聚合函数：既不是分布式的函数以及代数式的函数称之为整体式聚合函数。

在对一个大的数据集进行聚合时，如果聚合函数是分布式函数或者代数式函数，那么可以采用分而治之的思想，可以将大的数据集为众多小的数据集，然后对每个小的数据集进行计算，最后对中间的计算结果进行汇总，从而得到整体的计算结果。

2.2 MapReduce

MapReduce是基于非共享的并行计算模型，该模型能够充分利用由多台机器组成的计算、存储、网络资源并行地处理计算任务， 适合处理与大数据相关的统计分析。

MapReduce并行计算模型与其它并行计算相比，主要有两个特点：一是其对串行任务与并行任务的隔离，以及计算任务能够在各个计算节点上独立地进行；二是编程模型简洁，学习成本低。MapReduce将计算分为两个阶段：Map阶段和Reduce阶段。首先，一个大的输入文件被分割成M块，分别由m个并行运行的Map任务进行处理，每个map任务以键值对的形式接收输入，对于每一个记录，将其转为的形式，然后由reduce任务进行处理，输出键值对。

2.3 NoSQL

关系型数据库自20世纪70年代诞生以来，在企业和政府的信息化建设中得到了广泛的应用，今天关系型数据依然发挥着重要的作用。然而，对于以PB衡量的大数据，关系型数据库不能很好地应对。这些数据的特点的是数据类型多样，包括结构化、半结构化，非结构化的数据，另一个特点是数据量大。非关系型的NoSQL数据库适合这类数据的存储。NoSQL具有三个特点：一是以Key-Value作为存储模型；二是保证数据的最终一致性；三是在保证应用不间断的情况下方便实现水平扩展。NoSQL数据库主要包括Cassandra、HBase、mongoDB等。这三种作为NoSQL数据库中的主流代表，在很多生产系统中得到了应用，在处理大数据时，能保持很好的性能，都是较为成熟的产品。当然，这几种NoSQL数据库的系统架构不一样，侧重点也不一样。HBase的文件系统基于HDFS，能与Hadoop的MapReduce并行计算框架无缝集成。由于本文选用的是Hadoop的MapReduce并行计算框架，因此NoSQL数据库采用HBase。

3 算法

算法除了实现MapReduce中的map接口和reduce接口之外，还实现了getPartition分区接口。Map函数根据关系模式R的n个属性（A1，A1，A3，...，An），形成2n个所有属性的可能组合，再取得相应属性的值作为键值，这样，在map阶段，每条输入记录将产生2n个中间的键值对。为保证每个Reduce任务的负载大致相同，分区算法通过抽样的方式，统计每个键出现的频率，以每个键的频率之和度量分区的负载，尽可能让每个分区的负载大致相等。Combine函数根据具有分布式或者代数式性质的函数M对数据进行聚合，把中间结果中具有相同key进行合并，形成一个键值对。Reduce的实现相与Combine相似，只是在输出的时候有差异，Reduce将最终结果保存至HBase数据库。

3.1 Map/Reduce实现

算法形式化描述：

//R由n个属性组成的关系模式

R={A1，A2，A3…，An}

//e为输入文件中一条记录

Map（e）

{

//根据关系模式R和e产生中间的key

//每个输入元素e产生2n-1个key

emitKeyBySubSetOfR（0，n，R，e）

}

emitKeyBySubSetOfR（begin，end，R）

{

//计算包含R[i]的子集

for（i=begin；i

{

stack.push（R[i]）；

}

//i自增，计算不包含R[i]的子集

emitKeyBySubSetOfR（i+1，end）；

//I为R的一个子集

I={}

for（each o in stack）

{

I=I∪o

}

//元素e取I中的属性形成键值k

k=I（e）

emit（k，e）

stack.pop（）；

}

//中间结果保存到文件

Combine（k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2file（k，total）；

}

计算最终结果并保存至hbase数据库

Reduce （k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2hbase（k，total）；

}

3.2 Partition实现

每个Map任务会输出一系列的以键值对（）形式的记录，然后由Reduce任务进行处理。由于存在多个Reduce任务，具体的一条记录由哪个Reduce任务处理，是由分区函数决定的。Hadoop中缺省采用hash函数对Map任务输出记录的键值进行分区，由于每个分区只由一个Reduce任务处理，因此分区的数量等于Reduce任务的数量，每个Reduce任务处理一个分区。分区函数的形式描述为：

hash （Hash code （Intermediate-key） % numReduceTasks）

Hadoop中的Java实现如下：

public class HashPartitioner extends Partitioner {

public int getPartition（K key， V value，

int numReduceTasks） {

return （key.hashCode（） & Integer.MAX_VALUE） % numReduceTasks；

}

Hash函数能够保证每个分区中键（Key）的数量大致相同。假设有k个不同的键，由r个reduce任务处理，分区函数能够保证每个reduce任务处理键的数量为k/r。然而由于有的键（Key）频繁出现，即很多记录具有相同的键值，显然，分区中包含这样的键其数据量要大的多，所需的计算时间也更长。

建设有6个键，分别是K1，K2，K3，K4，K5，K6，每个键包含的记录数分别为1，2，3，4，5，6，这6个键由3个Reduce任务处理。采用hash分区策略，会形成3个分区，Partition1包含K1和K4，Partition2包含K2和K5，Partiton3包含K3和K6。尽管每个分区包含键的数量都为2，但是每个分区的数据量不一致。Partition1包含5条记录，Partition2包含7条记录，Partiton3包含9条记录。理想的情况应该是每个分区包含7条记录。

为了达到图2中均匀分区的效果，需要自定义分区函数。分区函数需要事先知道键的分布频率，如果数据集比较大，扫描整个数据集并求出各个键的分布频率，所需的时间比较长。可对数据集进行抽样，只针对一小部分数据进行统计，数据抽样的时间与整个计算任务的时间相比，可忽略不计。

假设一个数据集中包含k个不同Key，键值分别为K1，K2，K3，…，Kk，其出现的频率为f（ki），共有r个Reduce任务。每个Reduce任务的负载定义为其相应的分区的大小，分区大小可用该分区内记录数量大数目衡量，即分区内各个Key的频率之和。

分区算法的目标是让各个LRi的值尽可能接近。

R=new ArrayList（）；//初始时，每个Reduce的负载为0

K = {K1， . . . ， Kk}；//K为待分区的key的集合

While（K.length>0）//如果还有Key没有分配到某个Reduce中

{ //选取频率数最大的分配给某个Ri

kmax = argmaxk∈Kf（k）

//从待分区的key集合中移除

K.remove（kmax）

//如果存在某个Ri没有负载

if（R.length < r）

{ keylistofRi={}；

keylistofRi.add（kmax）；

//直接将该key分配给Ri

R.add（keylistofRi）；

}

//如果所有的Ri都有负载，那么将该key分配给目//前负载最小的Ri

else

{

keyListOfminLRi = argminiRi∈RLRi

R.remove（keyListOfminLRi）

keyListOfminLRi.add（kmax）

R.add（keyListOfminLRi）

}

}

return R；

这样，分区函数P能够将Ki分配给Rj处理，记为P（Ki， Rj）。通过抽样形成的分区方案存入分布式缓存当中，每个map任务按照分布时缓存中的分区方案P（Ki， Rj）对数据进行分区。

4 实验

为测试数据立方体计算的空间需求和性能，采用8个节点组成的Hadoop集群，每个节点的CPU为4核3.1GZ，内存为4GB，本地存储为500G，操作系统环境为Windows Server 2003。每个节点分别运行一个Map任务和Reduce任务，输入数据为根据Zipf分布人工合成，数据的倾斜程度通过参数z值控制，z的取值范围是[0，1]，较大的z值表明更高的倾斜程度。

每个输入Map接收500万条记录，输入数据共4000万条记录。每个记录包含4个属性，其中一个属性的类型为数字，作为度量维度，另三个为字符类型，作为属性维。聚合函数采用具有分布式函数特性的sum函数。

为在数据抽样的比例和精确性之间进行平衡，通过多次试验，发现以5%的比例进行抽样时，误差较小。按这个比例进行数据抽样时，数据抽样的完成时间为[5-8]s，这个时间与几百秒的计算任务而言，可忽略不计，以下有关完成时间的描述，均未将抽样时间计算在内。

当取z=0，即数据均匀分布，分区算法采用Hadoop中的缺省分区函数时，最快的Reduce任务用时130s，最慢的用时131s；当采用自定义分区函数时，最快的用时132s，最慢的用时132.5s。

当取z=0.6，即数据出现较高程度的倾斜，分区算法采用Hadoop中缺省分区函数时，最快的Reduce任务用时90s，最慢的用时331s；当采用自定义分区算法时，最快133s，最慢的用时138s。

随着z取更高的值，两个分区算法性能差异明显，一度出现缺省分区函数比自定义分区函数慢6倍的情况。

显然，自定义分区算法在输入数据无重复的情况下，性能与默认的分区函数相当，然而当输入大量重复，发生倾斜时，自定义分区函数获得的性能提升非常明显。

当属性维度分别从3增加为6和8时，不管采用何种分区算法，计算时间呈现指数级增长的趋势，这主要和每个输入记录产生2n个中间记录有关。

5 结束语

本文基于开源的Hadoop框架对完整数据立方体的计算进行了初步探索。Hadoop并行计算框架非常优秀，简化了并行计算的编程模型，使得并行数据立方体的计算很容易实现。然而，数据立方体的计算性能非常重要，数据分区是影响性能的一个重要因素，因为并行计算的前提是各个计算任务的负载大致相同。Hadoop的缺省分区机制在多数场合能够让每个Reduce任务的负载大致相同，然而在数据高度倾斜的情况容易导致计算偏斜。

本文从优化数据分区着手，采用抽样方式对分区算法进行了一定优化，当目标问题为分布式或者代数式的集合函数时，能够在一定程度上解决因为数据倾斜而导致的数据立方体的计算性能问题。

在系统架构方面，选用HBase存储数据立方体，以便水平扩展，应对数据立方体积快速增加的问题。实验结果表明，性能提升明显。此外，影响Hadoop的性能的因素有很多，比如集群的数量和集群中计算节点的数量，每个计算节点中运行的map任务和reduce任务的数量，以及网络带宽的情况，还有数据复制因子的影响，这些在未来的研究中也会涉及到。

参考文献

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F. Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者简介：

张子浪 （1978-），男，中国社会科学院研究生院，MBA，工程师；主要研究方向和关注领域：多维数据聚合。

葛昂，男，北京大学，MBA，高级工程师；主要研究方向和关注领域：数据挖掘、企业架构。

郑家民，男，北京航空航天大学，软件工程，高级工程师；主要研究方向和关注领域：数据挖掘、企业架构。endprint

为在数据抽样的比例和精确性之间进行平衡，通过多次试验，发现以5%的比例进行抽样时，误差较小。按这个比例进行数据抽样时，数据抽样的完成时间为[5-8]s，这个时间与几百秒的计算任务而言，可忽略不计，以下有关完成时间的描述，均未将抽样时间计算在内。

当取z=0，即数据均匀分布，分区算法采用Hadoop中的缺省分区函数时，最快的Reduce任务用时130s，最慢的用时131s；当采用自定义分区函数时，最快的用时132s，最慢的用时132.5s。

当取z=0.6，即数据出现较高程度的倾斜，分区算法采用Hadoop中缺省分区函数时，最快的Reduce任务用时90s，最慢的用时331s；当采用自定义分区算法时，最快133s，最慢的用时138s。

随着z取更高的值，两个分区算法性能差异明显，一度出现缺省分区函数比自定义分区函数慢6倍的情况。

显然，自定义分区算法在输入数据无重复的情况下，性能与默认的分区函数相当，然而当输入大量重复，发生倾斜时，自定义分区函数获得的性能提升非常明显。

当属性维度分别从3增加为6和8时，不管采用何种分区算法，计算时间呈现指数级增长的趋势，这主要和每个输入记录产生2n个中间记录有关。

5 结束语

本文基于开源的Hadoop框架对完整数据立方体的计算进行了初步探索。Hadoop并行计算框架非常优秀，简化了并行计算的编程模型，使得并行数据立方体的计算很容易实现。然而，数据立方体的计算性能非常重要，数据分区是影响性能的一个重要因素，因为并行计算的前提是各个计算任务的负载大致相同。Hadoop的缺省分区机制在多数场合能够让每个Reduce任务的负载大致相同，然而在数据高度倾斜的情况容易导致计算偏斜。

本文从优化数据分区着手，采用抽样方式对分区算法进行了一定优化，当目标问题为分布式或者代数式的集合函数时，能够在一定程度上解决因为数据倾斜而导致的数据立方体的计算性能问题。

在系统架构方面，选用HBase存储数据立方体，以便水平扩展，应对数据立方体积快速增加的问题。实验结果表明，性能提升明显。此外，影响Hadoop的性能的因素有很多，比如集群的数量和集群中计算节点的数量，每个计算节点中运行的map任务和reduce任务的数量，以及网络带宽的情况，还有数据复制因子的影响，这些在未来的研究中也会涉及到。

参考文献

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F. Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者简介：

张子浪 （1978-），男，中国社会科学院研究生院，MBA，工程师；主要研究方向和关注领域：多维数据聚合。

葛昂，男，北京大学，MBA，高级工程师；主要研究方向和关注领域：数据挖掘、企业架构。

郑家民，男，北京航空航天大学，软件工程，高级工程师；主要研究方向和关注领域：数据挖掘、企业架构。endprint

为在数据抽样的比例和精确性之间进行平衡，通过多次试验，发现以5%的比例进行抽样时，误差较小。按这个比例进行数据抽样时，数据抽样的完成时间为[5-8]s，这个时间与几百秒的计算任务而言，可忽略不计，以下有关完成时间的描述，均未将抽样时间计算在内。

当取z=0，即数据均匀分布，分区算法采用Hadoop中的缺省分区函数时，最快的Reduce任务用时130s，最慢的用时131s；当采用自定义分区函数时，最快的用时132s，最慢的用时132.5s。

当取z=0.6，即数据出现较高程度的倾斜，分区算法采用Hadoop中缺省分区函数时，最快的Reduce任务用时90s，最慢的用时331s；当采用自定义分区算法时，最快133s，最慢的用时138s。

随着z取更高的值，两个分区算法性能差异明显，一度出现缺省分区函数比自定义分区函数慢6倍的情况。

显然，自定义分区算法在输入数据无重复的情况下，性能与默认的分区函数相当，然而当输入大量重复，发生倾斜时，自定义分区函数获得的性能提升非常明显。

当属性维度分别从3增加为6和8时，不管采用何种分区算法，计算时间呈现指数级增长的趋势，这主要和每个输入记录产生2n个中间记录有关。

5 结束语

本文基于开源的Hadoop框架对完整数据立方体的计算进行了初步探索。Hadoop并行计算框架非常优秀，简化了并行计算的编程模型，使得并行数据立方体的计算很容易实现。然而，数据立方体的计算性能非常重要，数据分区是影响性能的一个重要因素，因为并行计算的前提是各个计算任务的负载大致相同。Hadoop的缺省分区机制在多数场合能够让每个Reduce任务的负载大致相同，然而在数据高度倾斜的情况容易导致计算偏斜。

本文从优化数据分区着手，采用抽样方式对分区算法进行了一定优化，当目标问题为分布式或者代数式的集合函数时，能够在一定程度上解决因为数据倾斜而导致的数据立方体的计算性能问题。

在系统架构方面，选用HBase存储数据立方体，以便水平扩展，应对数据立方体积快速增加的问题。实验结果表明，性能提升明显。此外，影响Hadoop的性能的因素有很多，比如集群的数量和集群中计算节点的数量，每个计算节点中运行的map任务和reduce任务的数量，以及网络带宽的情况，还有数据复制因子的影响，这些在未来的研究中也会涉及到。

参考文献

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F. Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者简介：

张子浪 （1978-），男，中国社会科学院研究生院，MBA，工程师；主要研究方向和关注领域：多维数据聚合。

葛昂，男，北京大学，MBA，高级工程师；主要研究方向和关注领域：数据挖掘、企业架构。

郑家民，男，北京航空航天大学，软件工程，高级工程师；主要研究方向和关注领域：数据挖掘、企业架构。endprint