Paper Info
Title
Parallel skyline queries
Abstract
In this paper, we design and analyze parallel algorithms for skyline queries. The skyline of a multidimensional set consists of the points for which no other point exists that is at least as good along every dimension. As a framework for parallel computation, we use both the MP model proposed in (Koutris and Suciu, PODS 2011), which requires that the data is perfectly load-balanced, and a variation of the model in (Afrati and Ullman, EDBT 2010), the GMP model, which demands weaker load balancing constraints. In addition to load balancing, we want to minimize the number of blocking steps, where all processors must wait and synchronize. We propose a 2-step algorithm in the MP model for any dimension of the dataset, as well a 1-step algorithm for the case of 2 and 3 dimensions. Moreover, we present a 1-step algorithm in the GMP model for any number of dimensions.
Year
DOI
Venue
2012
10.1007/s00224-015-9627-3
Theory of Computing Systems
Keywords
Field
DocType
Skyline queries,Parallel computation,Grid partitioning
Skyline,Synchronization,Load balancing (computing),Computer science,Parallel algorithm,Theoretical computer science,Database theory
Conference
Volume
Issue
ISSN
57
4
1432-4350
Citations 
PageRank 
References 
20
0.66
24
Authors
4
Name
Order
Citations
PageRank
Foto N. Afrati11423337.08
Paraschos Koutris234726.63
Dan Suciu396251349.54
Jeffrey D. Ullman4130995226.28