水利普查成果数据立方体并行计算方法研究

唐珊珊，万定生，朱跃龙，余宇峰，朱 凯

（河海大学计算机与信息学院，江苏 南京 210098）

水利普查成果数据立方体并行计算方法研究

唐珊珊，万定生，朱跃龙，余宇峰，朱 凯

（河海大学计算机与信息学院，江苏 南京 210098）

水利普查成果数据具有数据量大、维度多、维度分层等特点，因此物化水利普查成果数据立方体，所需的时间空间成本非常高。提出一种基于 Map/Reduce 计算模型进行外壳片段立方体并行计算的新方法。实验结果表明，该方法能够有效地提高在大数据集上计算外壳片段立方体的效率，降低物化水利普查成果数据立方体的时间空间成本。将水利普查成果数据立方体应用于多维分析系统，从多方面清晰直观地展现水利普查成果数据。

水利普查；数据立方体；外壳片段立方体；Map/Reduce 技术

0 引言

水利普查是一项重大的国情国力调查，是国家资源环境调查的重要组成部分。开展水利普查是为了查清我国江河湖泊等的基本情况，建立国家基础水信息平台，展现水利普查成果数据，为国家经济社会发展提供科学可靠的基础[1]。联机分析处理（OLAP）向用户提供及时分析数据以辅助决策，在OLAP 中数据通常以数据立方体（Data Cube）[2]形式存储，数据立方体的物化可以大幅度减少查询响应时间，提高 OLAP 性能。但完全物化数据立方体通常需要非常高的空间和时间成本。为了提高数据立方体生成和查询效率，许多专家学者提出了 Iceberg Cube[3]，Condensed Cube[4]和 Quotient Cube[5]等物化方法，这些方法在多维分析应用中起着重要的作用。水利普查设计了 300 余项统计指标，包括 8 大专题、33 小类、近 1 亿个基本对象，使得水利普查成果数据具有覆盖面广、数据量大、维度多、维度分层等特点，数据维度可以达到 20 个，记录数也常常超过 106条。因此物化水利普查成果数据立方体需要极高的时间空间成本[6]。

基于上述背景，提出一种基于 Map/Reduce 的外壳片段立方体并行计算方法，提高水利普查成果数据立方体物化效率，最后将生成的水利普查成果数据立方体应用于多维分析系统展示。

1 水利普查成果数据立方体

1.1 水利普查成果数据主题设计

第一次全国水利普查涉及河流湖泊、水利工程、经济社会用水、河湖开发治理保护、水土保持和水利行业能力建设等情况及灌区和地下水取水井等8 大专题 33 小类近 1 亿个基本对象，包括 300 余个指标，2 000 余个普查数据项。经过全国各级水利普查机构审核、汇总分析等，形成了我国迄今最为全面细致、完整系统的涉水基础数据资源和规范权威的水利普查成果数据。

根据中国水利水电科学研究院研制的《水利普查成果分析基本主题设计》报告，将水利普查成果数据基本主题设计按四级层次进行规划，一级主题为水利普查的 6 个专业方向，普查中的灌区专项和地下水井、水源地作为水利工程并入水利工程类中，二级主题为水利普查各类对象，三级主题为水利普查对象的属性和关系分类主题，四级主题为分类主题下水利普查对象的主要指标相关主题。直接分析主题总计 271 个（直接分析主题为最末级主题，以及没有四级主题的三级主题（8 个）和四级主题（263 个）），水利普查基本主题表如表 1 所示。

表1 水利普查基本主题表

1.2 水利普查成果数据立方体设计

水利普查成果数据立方体数据模型的设计采用三级数据模型的方法，包括概念、逻辑和物理模型，分别对应的设计结果为信息包图、星型模型及物理数据模型等。

1）概念模型设计。概念模型设计即通常所说的需求分析，确定数据仓库所需要访问的信息，在需求分析阶段确定操作数据、数据源及一些附加数据，建立较为稳固的概念模型。由于数据仓库的多维性，利用传统的数据流程图进行需求分析已经不能满足需要。超立方体（hypercube）用超出三维的表示来描述一个对象，采用信息包图的方法在平面上展开超立方体，用二维表格表示多维特征。信息包图拥有 3 个重要对象，分别为指标、维度和类别。指标是在维度上衡量信息的一种方法，类别是为维度定义详细的分类。利用信息包图设计概念模型需要确定 3 大内容：指标、维度、层次类别。

2）逻辑模型设计。逻辑模型设计即设计星型图，星型图能够清晰地反映概念模型中各个实体间的逻辑关系，并在此基础上更好的组织检索和查询。其中，星型图拥有指标、维度和详细类别等 3 个逻辑实体。指标实体是位于星型图中间的实体，对应于概念模型中的指标对象；维度实体是位于星型图星角上的实体，对应于概念模型的维度对象，作用是限制用户的查询结果，同时将主要指标数据进行聚和，从而缩小范围。详细类别实体对应于概念模型中详细类别对象，1 个维度内的每个单元就是 1个类别，代表该维度内的 1 个单独层次。机电井主题星型模型如图 1 所示。

3）物理模型设计。根据逻辑模型设计阶段的星型图，将指标实体转化为物理数据库表，即事实表。事实表包括星型图中心的指标量和星型图角上的维度实体中层次最低单位的主码。维度实体通常也转化为数据库表，即维表，包括每一个维层次的主码和对应的值，维表的关键字是该维度实体对应的详细类别实体的主码。维表和事实表通过维表关键字相关联。

1.3 Map/Reduce

Google 公司提出的 Map/Reduce[7]是一种实现分布式计算任务的并行框架，是大数据并行计算的核心技术，它将海量数据处理任务划分为 Map 和Reduce 过程。其中，Map 过程将原始的海量数据划分为不同的数据子集，并根据用户自定义的 Map 函数来对每一个数据子集进行映射处理；Reduce 过程将 Map 过程处理后的结果根据用户自定义的 Reduce函数进行归约处理。Map/Reduce 不仅隐藏了复杂的底层分布式计算实现的细节，而且给用户提供了简单、易用的功能接口及与性能相关的调优参数，数据切割、任务调度、结点通信和系统容错等功能均由 Map/Reduce 框架自动完成。

1.4 外壳片段立方体

在数据仓库中，数据立方体可以用 Cube =（D，M）来表示。D ={D1，…，Dm} 是维度集合，其中m≥1，Di=（DHi，σ）表示一个维度属性，DHi表示 D所有层次组成的一个有序集合，即h 代表 Di的层次数，是维度 D的第j 个层次，σ 是 DHi维层次上的依赖或偏序关系；M ={M1，…，Mn}是度量集合，其中 n≥1，Mi表示一个度量属性。

为了便于论述，以水利普查数据中的机电井工程对象数据事实表为例，此事实表包括：行政区划（addvcd）、所在地貌类型（dmlx）、机电井类型（jdjlx）和水源类型（sylx）4 个维度和供水井数量（sl）1 个度量，如表 2 所示。

表2 机电井工程事实表

行政区划维分为省（province）、市（city）、县（county）3 个层次，即 DHaddvcd= （nprovince，ncity，ncounty)。其中，province 的最大成员个数 32，city 的最大成员个数 21，county 的最大成员个数 31。

图1 机电井主题星型模型

定义 1 外壳片段立方体 Shell Fragments Cube。对于一个 n 维的高维数据立方体 Cube（D，M），将维度属性集合 D ={D1，…，Dn} 按照互不相交的原则，分割为 k 个独立片段，物化这 k 个独立的片段并创建倒排索引。对于 M ={M1，…，Mn} 度量属性集合，创建 TID_measure 度量索引号对照表。

利用层次维编码具有前缀层次语义特性，求得各个维相应维层次属性的编码前缀及其 TID 关联关系。表 2 中维度 addvcd 中层次 city 的编码前缀及其TID 关联关系如表 3 所示。

表3 维层次 city 的编码前缀及其 TID 关联表

2 外壳片段立方体并行计算与查询

提出基于 Map/Reduce 计算框架的外壳片段立方体并行计算方法（Parallel Computation of Shell Fragments Cube，PSFC）。主要分为 Map 和 Reduce过程，具体描述如下：

2.1 并行计算算法

1）Map 过程。Map 过程接收数据子集，根据外壳片段划分方法保存的 FID_dimensions 表，Map函数对数据进行逐条处理，输出映射处理后的 key/value 键值对。分为以下 3 种情况：

a. 对于层次维片段，生成各个维层次的编码前缀 {PrefixB1，…，PrefixBh}，并处理成形式为＜ key =＜ FID，PrefixBi〉 ，value = TID 〉 的键值对，其中FID 代表片段编号，TID 代表行索引号。

b. 对于非层次维片段，每个片段采用 BUC 算法，从 ALL cuboids 向上深度优先生成其它 cuboids，即计算出该片段的完全数据立方体。并处理成形式为 ＜ key = ＜ FID，tuplei 〉，value = TID 〉 的键值对，其中 tuplei 代表可能的数据单元。

c. 对于度量属性，标记其 key 的第 1 个属性取值为 0，生成形式为 ＜ key = ＜ 0，TID 〉，value = measure 〉的键值对，其中 measure 代表度量取值。

Map 函数形式化描述如下：该并行计算方法在 Map 端的 shuffle 过程中，通过重新定义 Partition 函数的分发规则：将 Map 过程输出的所有键值对中，具有相同片段编号的 key/value 键值对分发到同一个 Reducer 上进行处理。

2）Reduce 过程。Reduce 过程接收 Shuffle 过程处理得到的属于同一组的数据集，交给自定义的Reduce 函数进行处理，由于同一个 Reducer 处理的键值对中 FID 取值相同，那么每个 Reducer 处理结果即为 1 个外壳片段或 TID_measure 表。数据处理分以下 3 种情况：

a. 对于层次维，将 key 值中 PrefixBi相同的键值对进行合并，其中 value 值求并集，处理输出形式为＜ key = PrefixBi，value = ＜ TID1，…，TIDj〉〉。

b. 对于非层次维，将 key 值中非层次维聚集单元相同的键值对进行合并，其中 value 值求并集，输出形式为 ＜ key = tuplei，value = ＜ TID1，…，TIDj〉〉。

c. 对于度量，即 key 值中第 1 个属性为 0 的键值对，处理输出形式为 ＜key= TID，value = measure〉。

输入。Shuffle 过程输出；

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

2.2 并行查询算法

并行查询算法也主要分为 2 个阶段：Map 和Reduce 过程。若查询条件中包含层次维，将其预计算为层次维编码或编码前缀。

1）Map 过程。遍历外壳片段立方体所有的键值对，查找出符合查询条件的键值对并输出；自定义Map 函数中定义 1 个全局变量 flag，以此减少 Map函数处理键值对数量，提高查询性能。

2）Reduce 过程。对 Map 过程处理所得的键值对，取其 value 值进行求交集运算，得到符合查询条件的索引号集合 QList。在 TID_measure 中取出QList 对应的度量值，根据给定的聚集函数，计算出用户所需的聚集结果。

并行查询输入输出如下：

5 根据给定聚集函数，聚集计算 QList 对应的度量值；

2.3 算法性能测试

本实验用到的 Hadoop 集群环境由 6 台机器组成，实现语言为 Java，平台为 Eclipse。采用水利普查机电井对象脱密数据，包含 10 个维度和 5 个度量，在实验前已对各字段都进行了规范化处理。实验对外壳片段立方体传统方法和 PSFC 方法在数据量由（1～5）×106条构造时间进行比较。如图 2 所示。

图2 不同数据量 PSFC 与传统方法构造时间比较

由图 2 可以看出，当数据量较少时，由于集群需要额外的通讯和数据传送等开销，PSFC 方法的优势不太明显，构造时间大约是传统方法的 2/3；但随着数据量的不断增大，PSFC 方法的优势会越来越明显，到 5×106条数据时，构造时间小于传统方法的1/4。综上所述，PSFC 方法在计算高维、数据量大的数据立方体时有显著的优势，可支持水利普查多维度、大数据量的数据立方体计算。

3 水利普查成果数据多维分析系统

首先，采用 PSFC 算法计算出水利普查成果数据的各个外壳片段立方体；然后，利用开发工具Eclipse，采用 Java，JSP，Groovy，FusionCharts 等技术，使用预计算的外壳片段立方体数据，搭建水利普查成果数据多维分析系统。分析系统页面至左向右分为 3 个部分，第 1 部分根据需要逐级选取所需分析的主题，第 2 部分选择相应的分析维度，第3 部分以表格、柱状图或图形的方式展现水利普查成果数据分析结果。

分析系统可提供切片、切块、旋转、上卷、下钻等 OLAP 操作，对于有层次结构的维度，点击相应维度实现钻取下一层次的数据，具体实现如图 3所示。如柱状图显示的是全国各省所有机电井工程2011年取水量，点击某省可获取该省各市机电井工程 2011年取水量，如果继续点击某市，可获得该市下各个区的机电井工程 2011年取水量。

4 结语

外壳片段立方体并行计算和查询方法，相对于串行外壳片段立方体，在高维、数据量大时有显著的优势，可支持水利普查多维度、大数据量的数据立方体计算与查询。将计算出的外壳片段立方体应用于系统展示，清晰简洁直观地展现水利普查成果数据，向用户提供及时分析数据以辅助决策。当然，本方法还有很多需要研究和改进的地方，比如增量更新维护方面的性能表现，以及如何进一步加快查询响应时间等方向，都值得继续研究。

[1] 庞进武，程益联，罗志东. 水利普查与信息化[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] 朱凯，万定生，程习锋. 水利普查成果分析中数据立方体计算研究[J]. 计算机与数字工程，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 水利普查数据多维分析系统页面

TV21

A

1674-9405(2015)04-0001-07

2015-03-25

水利部公益性行业科研专项经费项目（201501022）

唐珊珊（1993－），女，四川广安人，硕士研究生，研究方向为数据挖掘与知识发现。