基于MapReduce的Skyline查询算法研究

摘要

Skyline查询是一个典型的多目标优化查询，在多目标优化、数据挖掘等领域有着广泛的应用。现有的Skyline查询处理算法大都假定数据集存放在单一数据库服务器中，查询处理算法通常也被设计成针对单一服务器的串行算法。随着数据量的急剧增长，特别是在大数据背景下，传统的基于单机的串行Skyline算法已经远远不能满足用户的需求。本文针对大数据背景下Skyline查询的应用需求，研究了基于MapReduce的Skyline查询处理方法。本文所做主要研究工作如下：
　　1）基于流行的分布式编程框架MapReduce，提出了适用于大数据集的分布式并行Skyline查询算法BAPS（Balanced Angular parallel Skyline）。BAPS算法针对影响MapReduce计算的因素，对现有基于角度的划分策略进行了改进，提出了Balanced Angular划分策略，该策略将所有数据的各维弧度的均值作为划分基准，将k维空间划分成了2k-1个数据量基本相等的区域，使得集群的负载更为均衡；同时，为了减少Reduce阶段的计算量，提出了在Map端使用局部Skyline点进行数据过滤的策略。实验结果显示本文提出的分布式并行Skyline查询算法BAPS能显著提升查询的性能。
　　2）针对不确定数据集在离散情况下的概率Skyline（P-Skyline）查询问题，提出了一个基于MapReduce的三阶段（预处理阶段、计算阶段和汇总阶段）解决方案。预处理阶段首先将数据对象按各自的Hilbert值进行排序，使得空间上距离较近的点排列到一起，然后基于排序后的数据集构建优化的最小剪枝集合，从而确保计算阶段的剪枝力度尽可能大；与此同时，对数据集计算了基于角度的优化划分。在计算阶段，为了提升剪枝的效率，提出了基于维度最优值的分级策略，能够根据数据所在的级别快速判断其是否将被过滤。实验结果显示文中提出的解决方案在高维空间中有着良好的效果。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题研究背景及意义

1.2 研究现状

1.3 研究内容与章节组织

第二章 基本概念与相关理论

2.1 Skyline查询

2.2 不确定数据集上的概率Skyline查询

2.3 Hilbert曲线相关知识

2.4 MapReduce计算框架

2.5 本章小结

第三章 基于角度划分的分布式并行Skyline查询算法

3.1 理论基础

3.2 BAPS算法

3.3 实验设计

3.4 本章小结

第四章 基于三阶段策略的概率Skyline查询算法

4.1 理论基础

4.2 SHVPS算法

4.3 实验设计

4.4 本章小结

第五章 总结与展望

5.1 本文总结

5.2 未来工作展望

参考文献

发表论文和科研情况说明

致谢