MapReduce框架下基于超平面投影划分的Skyline计算

摘要

近年来,Skyline计算在决策应用中起着越来越重要的作用.针对单机处理的研究已较为成熟.现今大数据爆炸,Skyline计算面临着大数据处理的问题.MapReduce是一个并行模型,广泛应用于数据密集型应用处理中.众所周知,MapReduce处理要求任务是可分解的.Skyline计算在MapReduce上执行时,分解任务的方法有网格划分、基于角度的划分等.网格划分仅在数据维度较低时表现良好;基于角度的划分适用于低维和高维数据,但在划分前需要一个复杂并且费时的坐标转换过程.现采用一种与基于角度的划分类似的基于超平面投影的划分来分解数据集,这种划分适用于低维和高维数据,而且其在划分前的坐标转换较为简单.根据超平面投影的划分提出了一种在MapReduce上处理Skyline计算的算法MR-HPP(MapReduce with hyperplane-projections-based partition),并在该算法的过滤阶段提出了一种有效的过滤算法PSF(presorting filter).大量基于Hadoop平台的对比实验表明该算法的准确性、高效性和稳定性.