Efficient Optimization of Multiple Subspace Skyline Queries

We present the first efficient sound and complete algorithm (i.e., AOMSSQ) for optimizing multiple subspace skyline queries simultaneously in this paper. We first identify three performance problems of the naíve approach (i.e., SUBSKY) which can be used in processing arbitrary single-subspace skyline query. Then we propose a cell-dominance computation algorithm (i.e., CDCA) to efficiently overcome the drawbacks of SUBSKY. Specially, a novel pruning technique is used in CDCA to dramatically decrease the query time. Finally, based on the CDCA algorithm and the share mechanism between subspaces, we present and discuss the AOMSSQ algorithm and prove it sound and complete. We also present detailed theoretical analyses and extensive experiments that demonstrate our algorithms are both efficient and effective. Electronic Supplementary Material The online version of this article (doi:) contains supplementary material, which is available to authorized users. This work is supported by the NSF of USA under Grant No. IIS-0308001, the National Natural Science Foundation of China under Grant No. 60303008, and the National Grand Fundamental Research 973 Program of China under Grant No. 2005CB321905.