Efficient Computation of Group Skyline Queries on MapReduce

Abstract

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.