paper9 2016基于mapreduce的skyline查询算法
核心
划分策略：基于弧度的划分策略
-
MapReduce 框架下影响集群处理速度的两个重要因素:
l) Map 与 Reduce 之间的传输量 ;2) 分配到各个计算节点的计算量
如果不考虑 Map 与 Reduce 之间的传输量，算法将受到传输带宽的限制，并且如果中间结果较大， Map 需要将中间计算结果写入磁盘，从而带来了大量的磁盘1/0 。负载均衡问题是 MapReduce 计算中经常遇到的问题，如果任务划分得不合理，会导致整个计算过程受制于单个任务而造成瓶颈;并且对于拥有大量计算的任务来说，一且任务失败必须重做，更加影响计算进度。 Hadoop 可以通过设置任务重做次数来缓解这个问题，但也只能在预测到单个任务有可能失败时重新启动一个任务来计算，并不能真正解决负载的均衡性问题。 -
使用mapreduce对数据进行分区处理的一个关键地方，需要证明下面的性质：
-
MapReduce 计算框架原理如
图所示，一个 MapReduce 任务通常被分解为 Map 和 Re
duce 两阶段执行，任务开始时作业调度器为每一个 Hadoop
分布式文件系统 (HDFS) 中的数据分片启动一个 Map 任务:
将原数据以 (Keyl， Valuel>的键值对形式输入，运算产生中
间结果 (Key2 ， List(Values)) 。接着进行Combine 运算，该过
程将同一分片内具有相同 Key 值的 Value 值予以合并，然后
将结果传送给 Reduce 端， Reduce 将根据各 Key 值计算出的
最终结果予以输出。 Combine 通常会使用 Reduce 实例进行
初始化，这可以大大减少计算框架内数据的传输量，从而提升
计算框架的效率。
本文主要工作
- 提出了 Balanced Angular 划分策略(简称 BA);
- 为了减少 MapReduce 实施 BNL 算法时的Combine 以及 Reduce 过程的计算量，提出了在 Map 端过滤数据的策略。
在独立同分布的数据集中 Sky
line 点的数目为 sn=O( (ln n) ^(k-1)!) ，其中 n 为数据
的总个数 ， k 为数据的维度。由计算式可以看出 Skyline 点的
数目与进行 Skyline 查询的维度的关系最强。为此，本文设置
数据集分区数目为 ndiv=2^(k-1) (k是为 Skyline 查询的维度)。具
体来说， Balanced Angular 在数据集的每个球面坐标维度的
弧度均值处进行划分。球面坐标的计算方式如下。
二维数据点变换为球面坐标
后为一维值，Balanced Angular 划分策略选择数据集中各点
在该维度上的弧度均值作为划分角度
-
计算阶段：为了减少 Skyline 查询处理过程的计算量，在 Map 阶段从局部 Skyline 点中选出支配能力最大的前 1 个作为过滤值，以减小后续Combiner 以及 Reduce 阶段的数据计算量，从而加快算法的处理速度。 Skyline 计算的复杂度为 O(kn^2).其中 k 表示数据的维度 ， n 为数据个数。过滤的计算代价为O(kn）
-
-
该阶段完成后，会将由 Key 分割的各个逻辑分块内的局
部 Skyline 点再进行一次结果集汇总，得到最终数据集的
Skyline 结果集。与计算过程不同，汇总阶段只能设置一个
Reduce 任务以保证计算出来的结果是针对全局的 Skyline 。
汇总阶段不再使用过滤以及分区机制，仅将前一阶段的输出
作为输入，使用 BNL 算法进行一次 Skyline 计算。另外，汇总
阶段可以采用由 Hadoop 的 API 所支持的多任务提交方式与
计算阶段一起提交任务:该任务可以通过控制 job. waitFor
Completion( )为 true 的方式保证正式计算阶段的任务完成后
才开始执行本阶段的任务，避免了多次提交任务的麻烦。