论文部分内容阅读
近年来,随着互联网应用的迅速发展和云计算技术的广泛应用,数据存储量呈现爆炸式增长。如何在大规模数据集中找到人们感兴趣的数据,帮助人们做出有效的决断,是一个亟待解决的问题。Skyline计算用于解决多目标决策问题。从已有的研究内容来看,Skyline计算可分为集中式处理和分布式处理。集中式处理的研究相对较为成熟,包括BNL (block nested loop)、D&C (divide and conquer)和SFS (sort-filter-skyline)等多种算法。由于大数据的发展,分布式处理尤为重要。MapReduce模型由Google公司提出,该模型具有高容错性和良好的扩展性,适用于数据密集型应用处理。因此,将Skyline计算置于MapReduce模型下运行是一个很好的选择。Skyline计算在MapReduce模型上运行,需要考虑的问题是如何对数据集进行划分。目前已知的划分方法有随机划分、网格划分和基于角度的划分。随机划分简单,但是运行不稳定。网格划分仅适用于低维度数据集。基于角度的划分先将点的坐标投影到超球面上,然后根据超球面坐标对数据集进行划分。使用这种划分在求局部结果集时可以淘汰更多数据,但该划分前的坐标转换较复杂、费时。本文采用基于超平面投影的划分对数据集进行划分。该划分首先将点的坐标投影到超平面上,然后根据超平面坐标对数据集进行划分。这种划分方法继承了基于角度划分的优点,即划分后求出的局部结果集较小,同时弥补了基于角度划分的不足,即该划分前的坐标转换简单、省时。本文提出基于该划分下的Skyline计算算法MR-HPP (MapReduce with hyperplane-projections-based partition),然后从该算法的合并过滤阶段及MapReduce的Shuffle阶段入手,对计算过程进行了优化。为了验证MR-HPP算法的有效性,我们在Hadoop平台下对以上几种划分策略下的算法进行了大量的对比实验,实验结果表明,本文提出的MR-HPP算法具有良好的扩展性、高效性和稳定性。