Full Citation
Title: Towards Multidimensional Subspace Skyline Analysis
Citation Type: Journal Article
Publication Year: 2006
ISBN:
ISSN:
DOI: 10.1145/1189769.1189774
NSFID:
PMCID:
PMID:
Abstract: 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.
Url: https://dl.acm.org/citation.cfm?id=1189774
User Submitted?: No
Authors: Pei, Jian; Zhang, Qing; Yuan, Yidong; Lin, Xuemin; Jin, Wen; Ester, Martin; Liu, Qing; Wang, Wei; Tao, Yufei; Yu, Jeffrey Xu
Periodical (Full): ACM Transactions on Database Systems
Issue: 4
Volume: 31
Pages: 1335-1381
Data Collections: IPUMS USA
Topics: Methodology and Data Collection, Other
Countries: