论文部分内容阅读
随着数据库和存储技术的飞速发展,人们可采集和利用的数据规模到达了空前的水平,如何从中迅速而且准确的找到有用的信息,成为一个急需解决的问题。Skyline查询的目的是从多维数据集中找到那些不被其他数据所支配的数据,在数据挖掘、多目标决策等领域具有广泛的应用。然而随着数据规模的急速增长,单节点架构已经不能满足计算的要求,MapReduce框架作为一种并行编程框架,利用普通配置计算机组成的集群并行处理大规模计算任务,封装了集群中计算机之间的调度、错误处理、通信等复杂细节处理,擅长处理大规模数据的运算,且具有良好的可扩展性。目前基于MapReduce的计算研究已经取得了初步的进展,但已有的算法还远不能满足Skyline计算的要求,本文研究如何更加高效的在MapReduce框架下进行Skyline计算,主要工作及创新点如下:一、分析了现有基于MapReduce框架下的基本Skyline算法,发现这些算法都没有进行有效的预处理,而是简单的对数据集进行区域划分,基于此,本文提出一种高效的预处理 Skyline 查询算法 MRFS(MapReduce based Filter Skyline),对大数据集进行预处理,提取支配能力较强的点组成比较点集,在算法开始前先用比较点集对原始数据集进行过滤,预先排除掉大部分非Skyline对象,再对过滤后的数据集在Map阶段并行计算出局部Skyline集,最后合并到一个Reduce任务,得到最终的Skyline结果集。实验结果表明:该算法比现有的算法在时间效率上提高了 20～30%。二、目前对于高维数据空间的k-支配Skyline查询,尚没有将相关算法引入到MapReduce框架下实现。因此,本文将k-支配Skyline查询纳入到MapReduce框架中,根据不同场景,实现了三种算法,分别为基于MapReduce的两轮扫描算法(MR-TSA)、基于MapReduce的索引算法(MR-IBA)以及一种基于简单排序的k-支配Skyline改进算法(MR-SIA)。实验分析表明:上述三种算法具有高效性和可用性。