Parallelizing Skyline Queries for Scalable Distribution
Ping Wu
Caijie Zhang
Ying Feng
Ben Y. Zhao
Divyakant Agrawal
Amr El Abbadi
10th International Conference on Extending Database Technology (EDBT 2006)
[Full Text in GZIP PS Format, 350KB]
[Full Text in PDF Format, 433KB]
Paper Abstract
Skyline queries help users make intelligent decisions over complex
data, where different and often conflicting criteria are
considered. Current skyline computation methods are restricted to
centralized query processors, limiting scalability and imposing a
single point of failure. In this paper, we address the problem of
parallelizing skyline query execution over a large number of
machines by leveraging content-based data partitioning. We present
a novel distributed skyline query processing algorithm (DSL) that
discovers skyline points progressively. We propose two mechanisms,
recursive region partitioning and dynamic region encoding, to
enforce a partial order on query propagation in order to pipeline
query execution. Our analysis shows that DSL is optimal in terms
of the total number of local query invocations across all
machines. In addition, simulations and measurements of a deployed
system show that our system load balances communication and
processing costs across cluster machines, providing
incremental scalability and significant performance improvement
over alternative distribution mechanisms.