RSkycube: Efficient Skycube Computation by Reusing Principle

摘要

Over the past years, the skyline query has already attracted wide attention in database community. In order to meet different preferences for users, the skycube computation is proposed to compute skylines, or cuboids, on all possible non-empty dimension subsets. The key issue of computing skycube is how to share computation among multiple related cuboids, which classified into sharing strict space dominance and sharing space incomparability. However, state-of-the-art algorithm only leverages sharing strict space dominance to compute skycube. This paper aims to design a more efficient skycube algorithm that shares computation among multiple related cuboids. We first propose a set of rules named identical partitioning (IP) for constructing a novel structure VSkyTree. Moreover, we present the reusing principle, which utilizes both sharing strict space dominance and sharing space incomparability by reusing VSkyTree on parent cuboids to compute child cuboids. Then, in top-down fashion, we design an efficient skycube computation algorithm RSkycube based on the reusing principle. Our experimental results indicate that our algorithm RSkycube significantly outperforms state-of-the-art skycube computation algorithm on both synthetic and real datasets.