ISSN 1000-1239 CN 11-1777/TP

• 软件技术 •

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

1. 1(大连理工大学软件学院 辽宁大连 116024);2(大连理工大学计算机科学与技术学院 辽宁大连 116024) (wangshuyandlut@gmail.com)
• 出版日期: 2014-12-01
• 基金资助:
基金项目：国家自然科学基金项目(61225010,61432002,61173162,61300084)；微软亚洲研究院与中国科学院计算机网络信息中心合作项目

### Skyline Computing on MapReduce with Hyperplane-Projections-Based Partition

Wang Shuyan1, Yang Xin2, Li Keqiu2

1. 1(School of Software, Dalian University of Technology, Dalian, Liaoning 116024); 2(School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024)
• Online: 2014-12-01

Abstract: Recently, Skyline computing has been playing a more and more important role in decision-making applications. Centralized processing has become relatively mature. Today with explosion of big data, Skyline computing faces the same problem of big data processing. MapReduce is a parallel model and it is widely used in data-intensive processing. As we all know, processing on MapReduce requires the task be decomposable. There are some partition methods for Skyline computing on MapReduce, such as grid partition, angle-based partition and so on. Grid partition can only get good performance on low dimensional dataset. Angle-based partition applies to both low dimensional and high dimensional dataset. But it needs a complex and time-consuming coordinates conversion process before partitioning. In this paper, we employ a method similar to angle-based partition method called hyperplane-projections-based partition to break down our dataset. It applies to both low dimensional and high dimensional dataset and at the same time the coordinates conversion process before partitioning is very simple. We propose an algorithm to process Skyline computing on MapReduce called MR-HPP(MapReduce with hyperplane-projections-based partition) based on hyperplane-projections partition. Moreover, we propose an effective filter method called PSF(presorting filter) in the filter period of MR-HPP. Extensive comparative experiments based on Hadoop have proved that our method is accurate, efficient and stable.