Efficient Optimization of Multiple Subspace Skyline Queries

• 作 者: Zhen-Hua Huang Jian-Kui Guo Sheng-Li Sun Wei Wang
• 机 构: Department of Computing and Information Technology, Fudan University, Shanghai 200433, China
• 出 处: 计算机科学技术学报（英文版）
• 发表日期: 2008年1期
• 关键词: skyline query query optimization regular grid performance evaluation

We present the first efficient sound and complete algorithm (i.e., AOMSSQ) for optimizing multiple subspaces kyline queries simultaneously in this paper We first identify three performance problems of the naive 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.