基于MapReduce的连续概率Skyline查询  

Continuous Probabilistic Skyline Query Based on MapReduce

作　　者：单观敏 董一鸿[1] 何贤芒[1] 

机构地区：[1]宁波大学信息科学与工程学院,浙江宁波315211

出　　处：《计算机科学与探索》2016年第2期182-193,共12页Journal of Frontiers of Computer Science and Technology

基　　金：浙江省自然科学基金No.LY16F020003;国家自然科学基金No.61202007;宁波大学研究生重点课程建设No.ZDKC2012006~~

摘　　要：大数据对传统的Skyline研究产生了挑战,利用并行框架MapReduce计算大数据下的Skyline已成为一个研究热点。研究了不确定移动对象的Skyline查询问题,提出了一种MapReduce框架下基于事件跟踪的连续概率Skyline查询算法——MR-DTrack(domination-track algorithm based on MapReduce)。首先采用基于角度的划分方法保证负载均衡,通过预计算获取Skyline集可能变化的时刻,在Reduce阶段获取候选概率Skyline集;然后利用局部过滤点剪枝,减少计算开销;最后合并计算出全局概率Skyline集。在人工数据集和真实数据集上的实验验证了算法的有效性。As big data has been a challenge to traditional Skyline research, computing Skyline using parallel frame- work of MapReduce is now a research hotspot. This paper studies a Skyline query of an uncertain moving object and proposes a continuous probabilistic Skyline query algorithm based on event tracking, named MR-DTrack （domination- track algorithm based on MapReduce）. Firstly, partitioning method based on angular is adopted to make workload bal- ance, a pre-computation is used to get the time when the Skyline sets change possibly, and the candidate probabilistic Skyline sets can be got in the Reduce stage. Then local filter points are used to prune in order to reduce computing costs. Finally, the global probabilistic Skyline set is computed by combining the candidate skyline sets. Experiments over artificial and real data sets prove the efficiency and effective of the new algorithm.

关 键 词：MAPREDUCE HADOOP 率Skyline 不确定移动对象 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]