基于MapReduce的预处理高效Skyline算法  

EFFICIENT PRE-PROCESSED SKYLINE ALGORITHM BASED ON MAPREDUCE

作　　者：李文俊[1] 张大方[1] 李玮[1] 

机构地区：[1]湖南大学信息科学与工程学院,湖南长沙410082

出　　处：《计算机应用与软件》2015年第3期243-246,278,共5页Computer Applications and Software

基　　金：国家自然科学基金项目(61173167);国家重点基础研究发展计划项目(2012CB315805);湖南省科技计划项目(2013SK3149)

摘　　要：现有基于MapReduce的算法不能高效地解决大数据的Skyline查询问题。针对这种情况,提出一种高效的预处理Skyline查询算法MRFS（MapReduce based Filter Skyline）,对大数据集进行预处理,提取支配能力较强的小点集组成比较点集,在算法开始前用比较点集对原始数据集进行过滤,排除掉一大部分不能成为Skyline结果集的数据对象;再对过滤后的数据集在Map阶段并行计算出局部Skyline集;最后合并到一个Reduce任务,得到最终的Skyline结果集。在不同数据分布下对该算法进行系统实验,结果表明算法比现有的算法在时间效率上提高了20%~30%。Existing MapReduce-based algorithms can not process Skyline query efficiently on big data. In view of this,we propose an efficient pre-processed Skyline query algorithm MRFS（ MapReduce-based filter Skyline）. It pre-processes big datasets and extracts small point-sets with stronger control abilities to form comparison point-set. Before the MRFS commence,the comparison point-set is used to filter the raw datasets to eliminate a great part of data objects which can not become Skyline outcome set; Then,for the filtered datasets,partial Skyline sets will be parallelly calculated in Map stage,and at last they are merged to a Reduce task to get final Skyline outcome set.Systematic experiments with different data distribution are conducted,results demonstrate that our algorithm improves the time efficiency by20% to 30% than the existing algorithms.

关 键 词：MAPREDUCE 大数据 SKYLINE 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]