Map-Reduce并行计算框架下的Skyline查询及优化算法

◆罗 云 陈佳瑜

Map-Reduce并行计算框架下的Skyline查询及优化算法

◆罗 云 陈佳瑜

（重庆理工大学 重庆 404100）

近几年来，Skyline查询处理在许多应用领域具有潜在的实用价值。在Map-Reduce框架下采用基于角度数据划分的方法，本文提出Cirl-Skyline查询算法。进一步提高算法的查询效率，为了更好的解决重复计算局部没有发生变化Skyline查询点的问题，在Cirl-Skyline算法的基础上提出Restrict-Skyline算法。理论分析和实验证实，该算法具有高效性和可扩展性。

Map-Reduce；Skyline查询；数据划分

0 前言

随着互联网的迅速发展，数据正在以前所未有的规模急剧增长，往往需要对海量数据进行挖掘分析才能得到真正有用的信息。Skyline查询[9]在近几年来迅速成为信息检索领域研究热点之一，且在数据的可视化方面有着广泛的应用。Skyline计算[8]就是从给定的数据库中搜索不被其它数据对象支配的数据对象集合。这里的支配[10]指的是一个数据对象p在任一维上都不比其它数据对象q“差”并且至少存在在某个维度上比q更“优”（“优”和“差”是根据用户个人偏好决定的）。

在Skyline查询计算中采用了Map-Reduce并行计算框架，使两者结合起来处理海量数据查询等问题。在Map-Reduce框架下采用基于角度数据划分的方法，提出了Cirl-Skyline查询算法。为了在Map任务前删除某些不能成为Skyline最终结果集的点，提高算法的执行效率，在Cirl-Skyline查询算法的基础上给出Restrict-Skyline查询优化算法。

1 相关概念及研究进展

1.1 相关概念

在数据空间P上定义d维的数据集D=（D1，D2，D3……Dd），其中Di（1≤i≤d）表示某时间的属性。Skyline结果集就是从某个数据库中抽取不被其它任何数据对象支配的数据对象的集合。

定义1（支配[10]）给定d维的数据集D上的两个数据点pi，qj，在任意一维度上pi（1≤i≤d）的取值都不小于数据点qj（1≤j≤d），且至少在某一维度上的取值pi比qj要大,称数据点p支配数据点q。

定义2（Skyline点[11]）在d维数据空间P上，数据集D中的任意点p∈D，则p为D的Skyline点；数据集D所有不被其它数据点支配的数据点集合，记为S，则S构成Skyline最终结果集。

1.2 研究进展

近年来，Skyline计算在数据挖掘等方面得到越来越多的关注。2001年，对Skyline计算用于数据库领域最早由Borzsonyi[1]等人提出。Borzsonyi提出了BNL和D&C算法。Tan K-L[2]提出了bitmap和Index算法。

由于数据规模超出了单机系统的计算能力，因此分布式Skyline计算用于解决指数级数据查询的问题得到研究者的关注。Balke[3]等人提出了BDS和IDS算法。Z.Huang[4]等人提出了在MANET上的第一个Skyline计算算法，将所有的移动设配组织成一个树状结构，并以发出查询的设备作为树的根节点。

面对指数级增长的海量数据，如何在现有算法基础之上提高Skyline查询效率，是一项长期的任务。

2 Map-Reduce框架下的Skyline查询算法

本节主要介绍Map-Reduce并行框架下的Skyline查询算法，给出具体Skyline查询算法-Cirl-Skyline查询算法，在Cirl-Skyline查询算法的基础上给出Restrict-Skyline查询优化算法。

2.1 数据区域划分方法

Map-Reduce以键值对对数据输入方式处理数据，能自动完成数据的划分。它包含Map和Reduce两个阶段并行处理模型和过程，Map负责把任务分解成多个任务，Reduce负责把分解后多任务处理的结果汇总起来。Map-Reduce模型如下方式表示:

Map:（k1，v1）→list（k2，v2）

Reduce:（k1，list（v2））→list（v3）

Skyline查询计算采用Map-Reduce“分而治之”的重要特征，将原有数据集划分多个子数据集进行并行计算。将数据点进行横、纵方向分割成若干部分。本文将采用基于角度的划分方法[10]。

基于角度的划分方法，采用文献[10]的划分方法。首先将数据点的笛卡尔积坐标映射到坐标上，然后根据球坐标将数据空间分成N个分区。球坐标计算公式如（1）所示，其中数据点P={P1，P2，P3，…Pn}，Pn为数据点的第n维属性；半径为r；维度为dk（1≤k≤n-1）的取值范围为［0］π，。

2.2 Cirl-Skyline查询算法

Map-Reduce将待处理的数据集分解成许多小的数据集，可以并行处理。Skyline计算由N个子任务串联而成，对于Skyline计算的最终数据集可以先计算局部Skyline结果集，并行计算数据块中的Skyline结果集合并形成局部的Skyline结果集，不断地重复上述操作，形成最终的Skyline结果集。

Cirl-Skyline查询算法的基本原理:根据角度划分的方法，将笛卡尔坐标空间映射到球面的空间，然后根据公式（1）的计算方法，计算数据点是属于某个区域，将数据点空间分成N个数据块。不断计算N个数据块的局部Skyline结果集，合并局部结果集，最后计算出全局Skyline结果集。

根据基本原理的介绍可以用Map-Reduce执行过程对Cirl-Skyline查询算法的实现。

（1）在Map阶段实现对数据区域分块操作。依次读取每一个数据点，采用基于角度划分方法，然后确定每个数据点属于某个区域块。

（2）将N个数据块的局部Skyline结果集合并。Reduce阶段根据BNL[1]算法进行过滤，最后计算出全局结果集。

根据角度划分方法与Map-Reduce下的Skyline执行过程，首先根据公式⑴计算出每个数据点坐标，在Reduce阶段使用BNL过滤算法，求出局部Skyline结果集。

以上简单的介绍了Map-Reduce下的Cirl-Skyline查询算法，通过采用BNL过滤算法减少Map输出。过滤阶段采用BNL过滤算法，采用两两比较方法。为了提高算法的运行效率，提出Restrict-Skyline查询优化算法，提高算法的剪枝能力。

2.3 Restrict-Skyline查询优化算法

Restrict-Skyline查询算法分为两部分:预处理和后序处理。首先对数据集进行预处理，对N个数据块中的数据点进行排序，采用SFS[7]算法中的F（P）值进行升值排序。设P（x1，x2，x3，…xn），F（P）随着维度的递增而递增，则F（P）是递增函数。

F（P）=a1×x1+a2×x2+…+an×xn，（ai>0，1≤i≤d）

数据块中的数据点根据F（P）成递增排序，设置局部过滤值，在Map任务未执行前，首先删除一些Skyline结果集的点，使得Reduce输入有所减少。数据点递增排序之后随机选取每个数据块中局部过滤值。合并局部Skyline结果集，根据F（P）再次将合并后的局部Skyline结果集进行排序，选取局部过滤值，删除部分局部Skyline结果集。通过减少局部Skyline结果集，提高合并效率和算法的运行时间。

3 实验验证与评估

3.1 实验环境

本文的实验在4台高配置的PC机组成的集群上运行且配置相同。处理器为Intel Core i7 4790GHZ，内存为4GB，操作系统为Windows 7。Hadoop版本为0.20.2，JDK的版本1.6。其中一台PC机为Master管理节点服务器，其余PC机为Slave节点。

实验数据是使用文献[1]中标准的数据，独立、相关和反相关数据集。数据集为2×105～2×106，数据维度是2～10，数据类型为浮点数，节点个数为6。三种数据集[1]如下:

⑴ 独立:数据的各维属性是相互独立且是均匀分布的。

⑵ 相关:数据的某一维属性的数值大（小），则数据的其它维属性随之也大（小）。

⑶ 反相关:数据的某一维属性的数值大（小），则数据的另一维或其它所有维属性都变小（大）。

为了直观看出，实验中的三种算法分别标记为MR-BNL、MR-CS、MR-RS。三种数据集分布对算法进行测试。

3.2 实验评估

本文提出了MR-CS和MR-RS查询算法与文献[11]提出的MR-BNL块嵌套循环算法进行相互比较，根据不同的数据集分布、维度变化以及节点个数、规模大小对算法运行时间进行比较从而验证算法的高效性。

3.2.1 维度变化对Skyline算法时间性能的影响

图1 维度变化对运行时间的影响

对于三种数据集分布，数据规模为2×106，节点个数为6。通过改变数据的维度，得到维度变化对Skyline查询运行时间的影响。如图1所示，图中表示数据服从三种数据集分布。对于独立和反相关分布，Skyline查询算法的运行时间在维度d∈[3，5]时，Skyline算法的运行时间呈现指数级增长。随着维度的增加，数据间的支配关系越少，从而在合并局部Skyline结果集时耗费大量的时间，同时影响算法的响应时间。但本文的两个算法运行时间仍小于MR-BNL运行时间，因为减少Map的输入量，从而提高运行效率。MR-RS采用角度划分方法和设置局部过滤值，删除局部Skyline结果集，待处理的数据点减少，因此减少处理时间，所以在三种数据分布下，MR-RS的运行时间较短。

3.2.2 规模变化对Skyline算法时间性能的影响

对于三种数据集分布，数据规模为2、4、6、8、10×105数据点，节点个数为6，维度为4的情况下的运行时间。随着数据规模以指数级增长时，Map-Reduce处理的任务量也在增加。MR-RS查询算法根据预先处理机制删除了局部Skyline结果集的点，从而减少了Map的输入量，因此MR-RS查询算法运行时间最短。对于反相关数据分布来说，反相关的数据彼此不支配的可能性增大，在合并Skyline结果集中耗费时间，从而运行开销也随之增加。从图2中可见，在三种数据分布下，MR-RS的性能最优，而MR-BNL算法的运行时间高于本文的两个算法，因为MR-RS在Map任务前删除不可能成为Skyline结果集的点，从而运行时间最短。

图2 数据规模对运行时间的影响

3.2.3 节点变化对Skyline算法时间性能的影响

对于三种数据集分布，测试节点数量对算法时间性能的影响。节点数设置成2、4、6、8。其他参数保持不变。并行计算的运行时间开销与节点数成反比，则算法的运行时间随着计算节点数增加反而减少。在独立和反相关数据分布情况下更加明显，MR-RS的时间开销随着节点个数的增加而减少，显然，随着计算节点增加到一定程度，算法的总体运行时间呈下降趋势，如图3所示。因此增加节点个数在一定程度上可以提高数据处理的能力，MR-RS的时间性能与预期的一致。

图3 计算节点对运行时间的影响

4 总结

本文针对海量数据的查询问题，将Skyline与Map-Reduce并行框架结合，实现了Cirl-Skyline查询算法和Restrict-Skyline查询算法。两种算法采用基于角度的划分方法，有效的过滤重复计算Skyline点，Restrict-Skyline查询算法设置约束范围和全局过滤值，减少Map任务的输入量，从而提高算法的运行效率。通过数据集对两种算法与MR-BNL算法进行比较，分别改变数据规模，节点个数和维度验证Skyline查询、Restrict-Skyline和MR-BNL算法在不同数据分布上运行时间的性能。实验结果表明，本文提出的Restrict-Skyline算法在不部分情况下运行效率高于Cirl-Skyline和MR-BNL算法，总体上提高了Skyline查询时间和计算效率。验证该算法的有效性和准确性。

[1]Borzsonyi S,Kossmann D,Stocker K.The Skyline operat or[C]//Proceedings of the 17th International Conference on Data Engineering（ICDE），2001.Washington，DC，USA:IEEE Computer Society，2001.

[2]Tan K L,Eng P K,Ooi B C.Efficient progressive Skyli ne computation[C]//Proceedings of the 27th International Co nference on Very Large Data Bases(VLDB),2001.San Francisco, CA,USA:Morgan Kaufmann.2001.

[3]Balke W T,Guntzer U,Zheng J X.Efficient distributed skylining for Web information systems[C]//Proc of EDBT,200 4.

[4]Huang Z,Jensen C S,Lu H,et al.Skyline queries against mobile lightweight devices in manets[C]//Proc of ICDE,200 6.

[5]Dean J,Ghemawat S.MapReduce:Sim plifi ed dat- a p roces sing on l arge clust er.Comm unications of the ACM, 2005.

[6]Kung H T,Luccio F,Preparata F P.On finding the ma xima of a set of vectors[J].J ACM,1975.

[7]丁琳琳，信俊昌，王国仁等.基于Map-Reduce的海量数据高效 Skyline查询处理[J].计算机学报，2011.

[8]张波良，周水庚，关佶红.MapReduce框架下的Skyl-i ne计算[J].计算机科学与索，2011.

[9]王淑艳，杨鑫，李克秋.MapReduce框架下基于超平面投影划分的Skyline计算[J].计算机研究与发展，2014.

[10]Chen L,Hwang K,Wu J.MapReduce Skyline query processing with a new angular partitioning approach.Proceedin gs of Parallel and Distributed Processing Symposium Worksh ops & PhD Forum（IPDPSW）,Sha-nghai，China，2012.

[11]Zhang Bo-Li ang,Zhou S hui-Geng,Guan JiHong.Ad apting Skyline com put at ion to the MapReduce framework: Algorithms and experiment s//Proceeding s of the DASFAA Workshop s.Hong Kong,China,2011.