Efficient Computation of Group Skyline Queries on MapReduce
Ming-Yen Lin, Yang, Chao-Wen, Sue-Chen Hsueh · Open Journal Systems (Global Science & Technology Forum) · 2016
Skyline query is one of the important issues in database research and has been applied in diverse applications including multi-criteria decision support systems and so on. The response of a skyline query eliminates unnecessary tuples and returns only the user-interested result. Traditional skyline query picks out the outstanding tuples, based on one-to-one record comparisons. Some modern applications request, beyond the singular ones, for superior combinations of records. For example, fantasy basketball is composed of 5 players, fantasy baseball of 9 players, and a hackathon of several programmers. Group skyline aims at considering all the groups comprising several records, and finding out the non-dominated ones. Because of the high complexity, few studies have been conducted and none has been presented in either distributed or parallel computing. This paper is the first study that solves the group skyline in the distributed MapReduce framework. We propose the MRGS algorithm to generate all the combinations, compute the winners at each local node, and find out the answer globally. We further propose the MRIGS algorithm to release the bottleneck of MRGS on unbalanced computing load of nodes. Finally, we propose the MRIGS-P algorithm to prune the impossible combinations and produce indexed and balanced MapReduce computation. Extensive experiments with NBA datasets show that MRIGS-P is 6 times faster than the MRGS algorithm.