MapReduce框架下的Skyline计算

计算机科学与探索 ›› 2011, Vol. 5 ›› Issue (5): 385-397.

MapReduce框架下的Skyline计算

张波良^1,2, 周水庚^1,2, 关佶红³

1. 复旦大学计算机科学技术学院, 上海 200433
2. 复旦大学上海市智能信息处理重点实验室, 上海 200433
3. 同济大学计算机科学与技术系, 上海 201804

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-01 发布日期:2011-05-01

Skyline Computation under MapReduce Framework

ZHANG Boliang^1,2, ZHOU Shuigeng^1,2, GUAN Jihong³

1. School of Computer Science, Fudan University, Shanghai 200433, China
2. Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China 3. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-01 Published:2011-05-01

摘要/Abstract

摘要： 由于Skyline查询广泛应用于多目标决策、数据可视化等领域, 近年来成为数据库领域的一个研究热点。针对云计算环境, 在MapReduce框架下设计并实现了Skyline算法。MapReduce是一个运行在大型集群上处理海量数据的并行计算框架, 其主要思想是任务的分解与结果的汇总。基于不同的数据划分思想, 实施了三种Skyline并行算法, 分别是基于MapReduce的块嵌套循环算法(MapReduce based block-nested- loops, MR-BNL)、基于MapReduce的排序过滤算法(MapReduce based sort-filter-skyline, MR-SFS)以及基于MapReduce的位图算法(MapReduce based bitmap, MR-Bitmap), 并针对这三种算法进行了系统的实验比较, 得出了不同数据分布、维数、缓存等因素对算法性能的影响结果。

关键词: Skyline计算, 云计算, MapReduce, 数据划分

Abstract: Skyline computation, due to its wide applications in multi-objective decision making and data visualization, has attracted many research interests in database community recently. Aiming at cloud computing applications, this paper addresses the problem of Skyline computation under the MapReduce framework. As a parallel programming model for data-intensive computing applications, MapReduce runs on a cluster of commercial PCs with the main idea of task decomposition and solution reduction. Based on different data division strategies, this paper proposes three algorithms: MapReduce based block-nested-loops (MR-BNL), MapReduce based sort-filter-skyline (MR-SFS) and MapReduce based bitmap (MR-Bitmap). It conducts extensive experiments to evaluate and compare the three algorithms under different situations of different data distributions, dimensions and buffer sizes.

Key words: Skyline computation, cloud computing, MapReduce, data division

张波良1,2 , 周水庚1,2 , 关佶红3 . MapReduce框架下的Skyline计算[J]. 计算机科学与探索, 2011, 5(5): 385-397.

ZHANG Boliang^1,2, ZHOU Shuigeng^1,2, GUAN Jihong³. Skyline Computation under MapReduce Framework[J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(5): 385-397.

[1]	吴虹佳，刘芳，刘斌，蔡志平. 分散计算：技术、应用与挑战[J]. 计算机科学与探索, 2020, 14(5): 721-730.
[2]	郑良汉，何亨，童潜，杨湘，陈享. 云环境中的多授权机构访问控制方案[J]. 计算机科学与探索, 2020, 14(11): 1865-1878.
[3]	张胜霞，田呈亮. 在幺模矩阵加密方法下的安全外包算法[J]. 计算机科学与探索, 2020, 14(1): 73-82.
[4]	陈彦橦，裴树军，苗辉. 云科学工作流截止期限约束代价优化调度算法[J]. 计算机科学与探索, 2019, 13(8): 1307-1318.
[5]	任晓莉，杨建卫，李乃乾. 云计算中基于动态虚拟化电子流密码的安全存储[J]. 计算机科学与探索, 2019, 13(8): 1331-1340.
[6]	赵倩，谢上钦，韩轲，龚青泽，冯光升，林俊宇. 远程直接内存访问与检查点相结合的容器迁移[J]. 计算机科学与探索, 2019, 13(12): 1995-2007.
[7]	李勇，滕飞，黄齐川，李天瑞. 基于Spark的时间序列并行分解模型[J]. 计算机科学与探索, 2018, 12(7): 1055-1063.
[8]	裴树军，宋冬梅，孔德凯. Map/Reduce下快速剪枝算法在复杂任务调度中的应用[J]. 计算机科学与探索, 2018, 12(1): 72-81.
[9]	刘沛东，安博，钟业弘，王虎，曹东刚. 私有云环境下基于虚拟集群的资源共享方法[J]. 计算机科学与探索, 2017, 11(8): 1204-1213.
[10]	张敬伟，尚宏佳，钱俊彦，周萍，杨青. 非均匀数据分布下的MapReduce连接查询算法优化[J]. 计算机科学与探索, 2017, 11(5): 752-767.
[11]	郭心宇，岳昆，李劲，武浩，张彬彬. 面向评价数据中用户偏好发现的证据理论方法[J]. 计算机科学与探索, 2017, 11(2): 231-241.
[12]	李东，邓泽航，李祖立. 基于MapReduce的XML结构连接处理[J]. 计算机科学与探索, 2016, 10(8): 1080-1091.
[13]	胡志刚，景冬梅，陈柏林，杨柳. 基于Hadoop平台的语义数据查询策略研究[J]. 计算机科学与探索, 2016, 10(7): 948-958.
[14]	单观敏，董一鸿，何贤芒. 基于MapReduce的连续概率Skyline查询[J]. 计算机科学与探索, 2016, 10(2): 182-193.
[15]	尹子都，岳昆，武浩，付晓东，刘惟一. 基于记忆曲线的数据密集型动态用户行为建模[J]. 计算机科学与探索, 2016, 10(10): 1376-1386.