MapReduce框架下的Skyline计算

被引：19

作者：

张波良 ^{[1
,2
]}

周水庚 ^{[1
,2
]}

关佶红 ^{[3
]}

机构：

[1] 复旦大学计算机科学技术学院

[2] 复旦大学上海市智能信息处理重点实验室

[3] 同济大学计算机科学与技术系

来源：

计算机科学与探索 | 2011年 / 05期

关键词：

Skyline计算; 云计算; MapReduce; 数据划分;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

由于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),并针对这三种算法进行了系统的实验比较,得出了不同数据分布、维数、缓存等因素对算法性能的影响结果。

引用

页码：385 / 397

页数：13