Efficient Optimization of Multiple Subspace Skyline Queries

We present the first efficient sound and completealgorithm (i.e., AOMSSQ) for optimizing multiple subspace skylinequeries simultaneously in this paper. We first identify threeperformance problems of the na\'\i ve approach (i.e., SUBSKY) which can beused in processing arbitrary single-subspace skyline query. Then wepropose a cell-dominance computation algorithm (i.e., CDCA) toefficiently overcome the drawbacks of SUBSKY. Specially, a novelpruning technique is used in CDCA to dramatically decrease the querytime. Finally, based on the CDCA algorithm and the share mechanismbetween subspaces, we present and discuss the AOMSSQ algorithm andprove it sound and complete. We also present detailed theoreticalanalyses and extensive experiments that demonstrate our algorithms areboth efficient and effective.