基于M apReduce的Skyline查询优化算法∗

杨 启 王 芳 黄树成

（江苏科技大学计算机科学与工程学院 镇江 212003）

1 引言

Skyline查询指从一个数据库中找到最优的数据集合。典型的Skyline查询例子如图1所示，某个游客去海滨城市旅游，他想找一个离海边近并且价格便宜的酒店。这时游客可以考虑选择折线上的点，那些不在折线上的数据点，其价格和距离没有折线上的点更优。

随着数据量的海量增长，传统的单服务器的串行算法已经不能满足人们的需求。MapReduce计算框架［3］广泛应用于大数据以及云计算处理中，因此可以用MapReduce框架来处理Skyline查询。在海量数据中，Skyline查询结果集远小于原始数据集，本文将支配能力较强的数据点优先地对数据进行过滤，能够有效地过滤一大部分非Skyline数据点，减少Map任务和Reduce任务的输入，使得查询效率更高。

图1 一个关于酒店的Skyline查询实例

2 相关工作

2.1 Skyline查询

Skyline的定义与性质:设d维的数据集S=（S1，S2，…，Sd），S 上每一维属性 S1，S2，…，Sd都是全序集，记全序关系为≺，对任意的 x，y∈Si，x≺y，表示x的取值优于y。全序关系可以根据用户偏好定义。

定义 1（支配［4］dominate）给定 d 维的数据集 S上的两个数据点 p=（p1，p2，…，pd）以及 q=（q1，q2，…，qd），称点p支配点q，当且仅当满足对于任意的i（1，d）都有 pi≤ qi，并且至少存在一个 i，使得 pi＜qi。

定义 2（数据点［5］Skyline）对数据集 S 上的任意点p，称p为S中的Skyline点，当且仅当在S中不存在支配点p的数据点。S中所有Skyline数据点的集合构成了关于S的Skyline数据集。

Skyline查询的概念最早由Borzsonyi等提出。BNL算法通过比较每个数据点的价值来找到Skyline点，由于时间复杂度为O（n2），计算时间随着数据点的增加而显著增加。此外 NN［6］和 BBS［7］算法应用多维索引如R-树结构来加快Skyline查询处理。在SFS算法［8］中指定一个单调函数，如果数据点p'的单调函数结果不大于数据点p，则意味着p不受p'的支配。利用这一特性，数据点根据单调函数的返回值按递减排序，在检查数据点是否是Skyline点时，数据点只需要与它之前的数据点进行比较。因此，数据之间的比较点的数量在BNL算法［1］进行可以减少。此外，文献［9］中提出的算法使用了一个额外的消除过滤器窗口，该窗口包含一组选定的数据点，以尽可能地消除非Skyline数据点。为了减少基于排序的方法所需的计算成本，Mamoulis等提出了动态索引技术［10］。当数据维度较高且数据量过大，分布式并行Skyline查询成为研究重点。

2.2 M apReduce并行计算框架

MapReduce是一个分布式并行计算框架，已经广泛运用于大数据计算中。MapReduce是一种编程模型，它可以开发可扩展的并行应用程序来处理大型集群机器上的大数据。理想情况下，MapReduce系统能在参与的机器之间实现高度的负载平衡，并尽量减少每个机器的空间使用、CPU和I/O时间，以及网络传输。它的基本思想是分治法，主要有两个部分组成:Map Task和Reduce Task，就是将大量的数据处理划分成多个子任务，每一个数据分片交给一个Map Task处理，Reduce Task负责对Map的结果进行汇总整理和输出。图2描述了MapReduce的数据处理过程。

图2 MapReduce的数据处理过程

3 改进的Skyline算法

3.1 原始的算法思想

原始的Skyline算法即将数据进行分区后，然后求出各个分区的Skyline结果，最后进行合并。由于原始数据集数量较多，将数据划分后，每一个进入Map阶段的Skyline查询的数据量仍然较多，并且每个数据点间需要进行比较，这样算法效率较低。然而通常情况下Skyline查询的结果集远小于原始数据集，为了提高算法的效率应尽量减少数据点间的重复比较。

3.2 改进的算法思路

本文对原始数据集进行预处理，优先选出支配能力较强的点，使用这些支配能力较强的数据点对数据集进行过滤，来减少数据点之间的重复比较。把这些数据点放入Map任务，设置一个自定义时间间隔，在一部分Map任务完成后将局部过滤值发送给Master节点，Master节点从这些局部过滤值中选择最优值作为全局变量，并发送给其他没有执行的Map任务，使用这些全局变量过滤Map任务，从而减少Reduce任务的输入量，提高算法的效率。

一个数据点的支配能力是指其支配其他数据点的能力，本文使用文献［12］中数据点支配能力的计算方法，d维的点qk的支配能力为。利用Map的输出默认按键值排序的功能，选取10个支配能力最强的点，将这10个点组成的比较点集放入第一个Map任务，让其能够优先成为全局过滤值，使得算法的过滤效果更加明显，减少那些在某个Map任务中成为Skyline结果的数据点被换下的可能性，降低了数据点之间的重复比较次数。

以二维空间为例，如图3所示，可以运用文献［13］的方法确定该点的支配能力，凡是位于该点的支配范围内的点，均是被该点支配的点，即一定不是Skyline查询结果，这里两维上的全偏序关系默认为小于关系。

图3 Skyline数据空间

图4 说明优化的Skyline查询算法。将原始数据放入4个Map任务，本文设定每个时间间隔内有2个Map任务完成，具体步骤如下:

步骤1将原始数据的比较点集放入第一个Map任务，在第一个时间间隔内，第一个和第二个Map任务完成后，产生各自的局部过滤值。第一个Map 任务的 Skyline 结果为（1，9），（2，7），（4，3），（6，2），（8，1），其局部过滤值为（4，3），第二个 Map任务的 Skyline结果为（5，3），（6，2），其局部过滤值为（6，2），将（4，3）和（6，2）作为局部过滤值发送给Master节点；

步骤 2 Master节从点（4，3）和（6，2）中选择点（4，3）作为全局过滤值发送给第一个和第二个Map任务；

步骤3使用全局过滤值点（4，3）过滤第一个Map任务和第二个Map任务的Skyline结果集，得到的结果分别是点（1，9），（2，7），（4，3），（6，2），（8，1）和（6，2），并将过滤后的结果发送给 Reduce任务；

步骤4将下一个时间间隔内中还没有开始的Map任务进行预处理，获取从Master节点传来的全局过滤值（4，3）来过滤Map任务的原始数据，使用全局过滤值（4，3）过滤第三个Map任务，全局过滤值可以支配点（5，9），（7，8），（10，3），（6，5），（5，6），则第三个Map任务的输入经过过滤后减少5个，第三个 Map任务的 Skyline结果集为（2，7），（8，1），（4，3），并将其局部过滤值（4，3）发送给Master节点，保证全局过滤值更新。全局过滤值（4，3）可以过滤第四个Map任务的所有原始数据集，被过滤的数据点一定不可能成为Skyline查询的最终结果，所以第四个Map任务的Skyline结果为空，不产生任何的输出。将过滤后的Skyline查询结果发生时给Reduce任务；

图4 优化的Skyline查询算法

步骤5以同样的方式过滤第五个Map任务，经过过滤后的 Skyline 结果集为（2，8），（3，6），（9，1），（1，9），并将过滤结果发送给 Reduce任务；

步骤6等到所有的Map任务完成后，Reduce任务将过滤所有的Skyline结果集，产生最终的Skyline结果；

将一段时间间隔内完成的Map任务的局部过滤值发送给Master节点，能够有效减少系统的等待时间。优化的Skyline查询算法能够降低Map任务的输入量，同时减少数据之间的重复比较次数，有效地提高了算法的效率。

4 实验分析

4.1 实验环境

本文的实验环境由5台PC机组成，每个PC机的配置为 Inter（R）Corei5-6500 CPU@3.20GHZ，4GB内存，操作系统为ubuntu11.10，其中一台PC机作为Master节点，其它4台PC机作为Slave节点。本文采用的Hadoop平台版本为0.20.2，在JDK1.6环境下编译。

本文的数据集利用文献［1］中的数据生成工具生成。实验数据集量为2×105到10×105，数据维度从2维到6维变化，默认维度是4，节点数为4。本文测试Skyline查询在独立分布和反相关分布情况下的性能。

本文从维度，数据量和节点数三个角度对Skyline查询时间进行分析比较，将本文的优化Skyline查询算法（Optimized Skyline Query Algorithm，OS）与文献［5］中的MR-BNL算法，MR-SFS算法进行比较。

4.2 实验结果

1）图5表示Skyline查询时间随数据量变化的情况，图 5（a）和图 5（b）分别表示独立分布和反相关分布三种算法的运行时间与数据量的关系图。随着数据量的增大，每个Map任务需要处理的数据量也增大，当数据量从2×105条增加到10×105条时，可以看出算法的开销增大。由于SFS算法是对BNL算法的改进，在数据量较小时，SFS算法的性能不能完全体现，当数据量较大时，SFS算法具有较高的时间性能。从图中可以看出OS算法的运行时间远低于MR-BNL算法和MR-SFS实验法，原因是OS算法能够在任务运行前过滤掉一大部分非Skyline数据，使得Map任务的输入量减少，同时OS算法能在最初始的阶段找出一些必定成为Skyline点的数据集，过滤效果更加明显，从而减少数据的换入换出，降低数据点之间的重复比较次数，所以算法性能最佳。由于反相关数据在某一维上的取值越大那它在其他维度上取值越小，这样使得互不支配的数据点更多，从而算法的运行时间比独立分布的时间较长。

图5 Skyline查询算法基于数据量的运行时间

2）图6表示Skyline查询时间随数据维度变化的情况，图 6（a）和图 6（b）分别表示独立分布和反相关分布三种算法的运行时间与维度的关系图。随着维度的增加，数据点的支配关系需要比较更多的维度，这样整个算法的时间开销都增大。从图中可以看出SFS算法的时间效率略高于BNL算法，而优化的OS算法随着维度的变化依然拥有较高的时间效率，主要是由于过滤点集的选取较优。在低维度的时候，三种算法的运行时间都较短，然而随着维度的增加，互不支配的数据也增多，数据间的比较增多，导致运行时间增加。当维度达到5维时，两种分布情况下的查询时间都急剧增加，出现“维度灾难”。在反相关数据下，当维度高于5时，三种算法的运行时间急剧增加，其主要原因是反向关数据的特点和Skyline查询支配的定义（一个数据支配另外一个数据指该数据的所有维度的取值都不比另外一个数据差，并且至少有一个维度是优于另外的一个数据）。在反相关数据中随着维度的增加，算法的运行时间会呈指数增加。

图6 Skyline查询算法基于维度的运行时间

3）图7表示Skyline查询时间随节点数变化的情况，图 7（a）和图 7（b）分别表示独立分布和反相关分布三种算法的运行时间与节点数的关系。随着节点数的增加，Skyline查询时间都在减少。从图中可以看出SFS算法的时间效率略高于BNL算法，而优化的OS算法在时间效率上依然高于SFS算法和BNL算法，主要是OS算法在节点数越多的时候过滤掉的数据点越多，并且并行处理更明显，算法运行时间越少。当节点较少的时候，系统的并行性和处理效率较低，能够设置的节点越多，系统的并行性和处理效率越强，算法的时间性能越优。

图7 Skyline查询算法基于节点数的运行时间

5 结语

由于传统的Skyline算法在大数据情况下效率较低，本文设计的算法对原始数据集进行过滤，过滤掉一些不可能成为Skyline结果集的数据点，该方法能在最初始的阶段找出一些必定成为Skyline点的数据集，使用这样的数据点来过滤其他Map任务中的数据，过滤效果更加明显。同时时刻更新全局变量，降低数据点之间的重复比较次数。大量实验表明，算法具有良好的可用性和高效性。