Towards multidimensional subspace skyline analysis

The skyline operator is important for multicriteria decision-making applications. Although many recent studies developed efficient methods to compute skyline objects in a given space, none of them considers skylines in multiple subspaces simultaneously. More importantly, the fundamental problem on the semantics of skylines remains open: Why and in which subspaces is ( or is not) an object in the skyline? Practically, users may also be interested in the skylines in any subspaces. Then, what is the relationship between the skylines in the subspaces and those in the super-spaces? How can we effectively analyze the subspace skylines? Can we efficiently compute skylines in various subspaces and answer various analytical queries? In this article, we tackle the problem of multidimensional subspace skyline computation and analysis. We explore skylines in subspaces. First, we propose the concept of SKYCUBE, which consists of skylines of all possible nonempty subspaces of a given full space. Once a SKYCUBE is materialized, any subspace skyline queries can be answered online. However, SKYCUBE cannot fully address the semantic concerns and may contain redundant information. To tackle the problem, we introduce a novel notion of skyline group which essentially is a group of objects that coincide in the skylines of some subspaces. We identify the decisive subspaces that qualify skyline groups in the subspace skylines. The new notions concisely capture the semantics and the structures of skylines in various subspaces. Multidimensional roll-up and drill-down analysis is introduced. We also develop efficient algorithms to compute SKYCUBE, skyline groups and their decisive subspaces. A systematic performance study using both real data sets and synthetic data sets is reported to evaluate our approach.