Parallel Dynamic Skyline Query Using MapReduce
Yuanyuan Li, Wenyu Qu, Zhiyang Li, Yujie Xu, Changqing Ji, Junfeng Wu · 2014
Dynamic skyline queries are useful in decision making and data-intensive applications. With the number of data increases, such skyline calculation is a challenging problem. Unfortunately, skyline query processing in centralized system is not suitable for the case. In this paper we propose a parallel algorithm which can calculate dynamic skylines with MapReduce. Firstly, we build an appropriate Inverted Grid Index structure. Secondly, the query point q is mapped to the matching cell of grid. We proposed a coarse-grained parallel algorithm for computing global skyline cells which can eliminate out the dominated cells with respect to q according to cell dominance relationship. The data points in global skyline cells can be as candidate set of dynamic skylines. It can reduce the cost of dynamic skyline by pruning out the data points in the dominated cells in advance. Finally, we check whether each point in the global skyline cells is dynamic skyline. Our experiments show that the efficiency of this mechanism compared to standard techniques without pruning.