Angle-based space partitioning for efficient parallel skyline computation

Recently, skyline queries have attracted much attention in the database research community. Space partitioning tech-niques, such as recursive division of the data space, have been used for skyline query processing in centralized, paral-lel and distributed settings. Unfortunately, such grid-based partitioning is not suitable in the case of a parallel skyline query, where all partitions are examined at the same time, since many data partitions do not contribute to the overall skyline set, resulting in a lot of redundant processing. In this paper we propose a novel angle-based space parti-tioning scheme using the hyperspherical coordinates of the data points. We demonstrate both formally as well as through an exhaustive set of experiments that this new scheme is very suitable for skyline query processing in a parallel share-nothing architecture. The intuition of our partitioning tech-nique is that the skyline points are equally spread to all partitions. We also show that partitioning the data accord-ing to the hyperspherical coordinates manages to increase the average pruning power of points within a partition. Our novel partitioning scheme alleviates most of the problems of traditional grid partitioning techniques, thus managing to reduce the response time and share the computational workload more fairly. As demonstrated by our experimen-tal study, our technique outperforms grid partitioning in all cases, thus becoming an efficient and scalable solution for skyline query processing in parallel environments. 1