arXiv:1611.00423v1 [cs.DB] 1 Nov 2016

Computing Skylines on Distributed Data
Haoyu Zhang

Qin Zhang

Indiana University Bloomington
Bloomington,IN,USA

Indiana University Bloomington
Bloomington,IN,USA

hz30@umail.iu.edu

qzhangcs@indiana.edu

ABSTRACT
In this paper we study skyline queries in the distributed
computational model, where we have s remote sites and a
central coordinator (the query node); each site holds a piece
of data, and the coordinator wants to compute the skyline
of the union of the s datasets. The computation is in terms
of rounds, and the goal is to minimize both the total communication cost and the round cost.
Viewing data objects as points in the Euclidean space, we
consider both the horizontal data partition case where each
site holds a subset of points, and the vertical data partition
case where each site holds one coordinate of all the points.
We give a set of algorithms that have provable theoretical
guarantees, and complement them with information theoretical lower bounds. We also demonstrate the superiority
of our algorithms over existing heuristics by an extensive set
of experiments on both synthetic and real world datasets.

1.

INTRODUCTION

Skyline computation, also known as the maximal vector
problem, is a useful database query for multi-criteria decision
making. If we view data objects as points in the Euclidean
space, then the skyline is defined to be the subset of points
that cannot be dominated by others, where we say a point y
dominates a point x if y dominates x in all dimensions. This
problem was first studied in computational geometry in the
mid-1970’s [10], and was later introduced into databases as
a query operator [4]. There is a vast literature on skyline
computation and its variants, and we refer readers to [6] and
[8] for excellent surveys.
Most work on skyline computation in the literature has
been conducted in the RAM (signal machine) model. In
recently years, due to the large size of the datasets and the
popularity of map-reduce type of computation, a number
of parallel skyline algorithms have been proposed [19, 15,
18, 17, 9, 1, 13, 14]. A common feature of these parallel
algorithms is that they use the divide-and-conquer approach,
that is, they use central mechanisms to partition the whole

Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
Copyright 20XX ACM X-XXXXX-XX-X/XX/XX ...$15.00.

point set into a number of subsets, and then assign each
subset to a machine for local processing; finally the local
results are merged to form the global skyline. The art of the
algorithm design in this line of work lies in how to choose
the partition mechanism.
In this paper we study the skyline computation on distributed data, which is different from parallel computation
in that the data is inherently distributed in different locations, and we cannot afford to repartition the whole dataset
since data repartition is communication prohibited over networks, and may also cause local storage and data privacy
issues which the query node cannot control.
Consider a global hotel search engine, where each hotel
is represented as a point in the 2-dimensional Euclidean
space with the x-coordinate standing for the price and the
y-coordinate standing for the rate of the location. A user
naturally wants to find a hotel with the best location and the
best price, although in reality hotels in good locations usually have higher prices. Thus a good search engine should
recommend the user with a list of candidates such that no
other hotel has both cheaper price and better location. This
list is exactly the skyline of the point set. Given a query, the
search engine (e.g., kayak.com, hipmunk.com) needs to contact servers/providers in different locations worldwide. The
total bits of communication between the query node and
servers and the communication rounds typically dominate
the engine’s response time, since sending messages through
network is much slower than local computation, and the initialization of a new communication round takes quite some
system overhead.
The Coordinator Model and Previous Work. We
study the skyline problem in the coordinator model which
captures the type of distributed computation mentioned above.
In this model we have s remote sites each holding a piece of
data, and a central coordinator which acts as the query node.
We assume there is a two-way communication channel between each site and the coordinator. The computation is in
terms of rounds: at the beginning of each round the coordinator sends a message to some of the sites, and then each of
the contacted site sends a response back to the coordinator.
The goal is to minimize the total bits of communication and
the number of the rounds of the computation. See Figure 1
for a visualization of the model.
We differentiate two scenarios of data storage at sites:
horizontal partition and vertical partition. In the former
each site contains an (arbitrary) subset of points. And in
the later each site contains one attribute of all points together with their IDs which are used to restore the whole

regardless of the communication rounds. We then propose a heuristic that works well in practical settings.
These are presented in Section 3.

Coor

one round

Site 1

Site 2

Site 3

···

3. We have implemented our algorithms and relevant heuristic algorithms in the literature, and run them on both
synthetic and real-world datasets. Our experiments
have demonstrated the superiority of our algorithms
over the existing ones in various aspects. We also noticed that for the horizontal partition and the datasets
we have tested, with only three communication rounds
the tradeoff algorithm can achieve similar communication cost compared with the theoretically optimal one.
The experimental results are presented in Section 4.

Site s

Figure 1: The Coordinator Model
point vectors. Thus if points have d dimensions, we have
d sites. The vertical partition corresponds to the settings
where the information of each attribute has to be retrieved
from a different server/provider. For example, we may want
to find the lowest prices of hotels from kayak.com, while the
customers’ best ratings from TripAdvisor.
The coordinator model is equivalent to the models used in
several previous works for distributed skyline computation
[15, 20] (horizontal partition) and [2, 12] (vertical partition).
However, all the existing skyline algorithms in this model are
heuristic in nature. We will briefly describe these algorithms
in Section 4.1 (horizontal partition) and Section 3.2 (vertical
partition) respectively. In [16] the authors studied a general
version of vertical partition where multiple columns can be
stored in one site. In this paper we will give algorithms
with provable theoretical guarantees (for vertical partition
we give a better heuristic, given a strong impossibility result
that we will show). We will also compare our algorithms
with previous ones experimentally in Section 4.
The Skyline Problem. We now give the formal definition of the skyline problem. In this paper we consider the
problem in the 2-dimensional Euclidean space. Given two
distinct points u = (xu , yu ) and v = (xv , yv ), we say u dominates v, denoted by u  v, if xu ≥ xv and yu ≥ yv . For a
set of distinct points S, the skyline of S is defined to be
sk(S) = {u ∈ S | v ∈ S, if v  u then v = u}.
We next define the data partition of the skyline problem
in the coordinator model. In the horizontal partition case,
each site i holds a set Si ⊆ S. In the vertical partition case,
we have two sites; the first site holds {(xu , IDu ) | u ∈ S}
where IDu denotes the ID (key) of point u, and the second
site holds {(IDu , yu ) | u ∈ S}. In both cases, the coordinator
needs to output sk(S) at the end of the computation.
Our Contribution. We have made the following contributions in this paper. Let n be the total number of points, k
be the number of skyline points (i.e., the output size), and
s be the number of sites.

Preliminaries. Let [n] denote {1, 2, . . . , n}.
The φ-quantile of a set S is an element x such that at most
φ |S| elements of S are smaller than x and at most (1−φ) |S|
elements of S are greater than x. If an -approximation is
allowed (denoted by (φ, )-quantile), then we can return any
φ0 -quantile of S such that φ −  ≤ φ0 ≤ φ.

2.

HORIZONTAL PARTITION

In this section we give two algorithms for skyline computation in the horizontal partition case. We then complement
them by proving that the first algorithm is optimal in terms
of the total communication cost (though it may need a large
number of rounds). On the other extreme, if we want the
computation to be done in one round then in the worst case
the sites need to send almost everything to the coordinator.
Our second algorithm gives a tradeoff in between.
We also show that if data is sorted among the sites according to one of the coordinates, then there is a simple
algorithm that has much smaller communication cost and
uses only two rounds.

2.1

Algorithms

There is a simple algorithm for computing the skyline
points in the coordinator model in one round: Each site
computes the skyline of its local data points and sends it
to the coordinator, and then the coordinator computes the
global skyline on top of the s local skylines. Unfortunately
this algorithm has communication cost Ω(n); in other words,
in the worse case almost all points in all sites need to be sent
to the coordinator. We enclose a proof for this statement in
Section 2.2.2. We thus try to explore if more rounds can
help to reduce the communication cost.

2.1.1

Algorithm with Optimal Communication Cost

1. For the horizontal partition, we propose two algorithms.
The first one achieves the theoretically optimal communication cost Θ(ks), but needs dk/2e communication rounds. The second one gives a tradeoff between
the total communication cost and rounds: given a
round budget r the algorithm uses roughly O(skn2/r )
communication (see Theorem 2 for the precise bound).
We also prove that any one-round algorithm needs
linear (i.e., Ω(n)) communication in the worst case.
These are presented in Section 2.

Our algorithm with communication cost O(ks) is described
in Algorithm 1. We will show in Section 2.2.1 that this
communication cost is in fact optimal1 even if we allow an
infinite number of communication rounds.
Let us explain Algorithm 1 in words. At the beginning,
each site computes its local skyline points since only these
points can possibly be the global skyline points. The rest
of the algorithm works as follows. At each round, the coordinator tries to find the (at most two) points with the
largest x-coordinate or y-coordinate in the remaining points
held by all sites. This is done by asking all sites to report

2. For the vertical partition, we first prove that in the
worst case, any algorithm needs linear communication,

1
Up to a logarithmic factor which counts the number of bits
used to represent a point.

the local maximums of their remaining points (Line 3-5).
Next, the coordinator computes new global skyline points
from the received local maximums, and then sends the new
global skyline points to all sites for another local pruning
step (Line 6-9).
We now show the correctness of Algorithm 1 and analyze
its costs. First, it is clear that the points with the largest
x-coordinate or y-coordinate must be on the skyline. After the pruning, the points with the largest x-coordinate or
y-coordinate in the remaining points also must be on the
skyline since they cannot be dominated by the other remaining points as well as the previous skyline points. We
thus can find one or two skyline points in each round (finding one skyline point may only happen in the last round).
Since there are at most k skyline points, the algorithm will
terminate after at most dk/2e rounds.
The running time at each site consists of two parts: the
computation of the local skylines and the point prunings.
The computation of local skyline at the i-th site needs O(ni log ni )
time [10], where ni = |Si | is the number of points at the ith site. The time used for pruning is linear in ni at the
i-th site: when pruning points using the new skyline point
with the global maximum y-coordinate (Line 8), we scan
the points which are sorted increasingly according to their
x-coordinates after the local skyline computation. If a point
cannot be pruned in a particular round, then all the points
after it with larger x-coordinates cannot be pruned in this
round. Therefore every point will only be pruned once in the
whole computation. Same arguments hold for the prunings
using the new skyline point with the global maximum xcoordinate. At the coordinator, for each round we only need
to compute the maximums over at most 2s points. Thus the
total running time is bounded by O(ks).
Theorem 1. There exists an algorithm for computing the
skyline on n points in the 2-dimensional Euclidean space
in the coordinator model with s sites and horizontal data
partition that uses O(ks) communication and dk/2e rounds,
where k is the output size, that is, the number of points in the
skyline. The total running time at the i-th site is O(ni log ni )

14
Tradeoff by Algorithm 2
Optimal communication cost by Algorithm 1

13

Communication Cost (log)

Algorithm 1 Optimal Communication under Horizontal
Partition
Input: Si is initialized as the point set held by Site i
Output: the global skyline
1: Site i computes its local skyline points and discards the
other points in Si
2: while ∃i ∈ [s] s.t. Si 6= ∅ do
3:
for each i s.t. Si 6= ∅ do
4:
Site i sends the point with the largest xcoordinate and the point with the largest y-coordinate
to the coordinator
. the two points can be the same
point
5:
end for
6:
The coordinator computes new global skyline points
from the points received from all sites, and sends the
new global skyline points to each site
7:
for each i s.t. Si 6= ∅ do
8:
Site i prunes Si by new global skyline points received from the coordinator
9:
end for
10: end while

12
11
10
9
8
7
6

0

20

40

60

80

100

Round

Figure 2: Theoretical Communication-Round Tradeoff
where ni is the number of points at the i-th site, and that at
the coordinator is O(ks).

2.1.2

A Communication-Round Tradeoff

In the previous section we have shown an algorithm with
the optimal communication cost but needs dk/2e rounds; on
the other hand, there is a naive one-round algorithm but in
the worst case it needs Ω(n) bits of communication. The
natural questions is:
Can we obtain a communication-round tradeoff
to bridge the two extremes?
We try to address this question by proposing an algorithm
that allows the users to choose the number of the rounds of
the communication in the computation. In this section we
show the following result.
Theorem 2. There exists an algorithm for computing the
skyline on n points in the 2-dimensional Euclidean space in
the coordinator model with s sites and horizontal data partition that uses r (≥ 3) rounds and C = O(sk(n/s)1/dr/2e )
communication, where k is the output size, that is, the number of points in the skyline. The total running time at the
i-th site is O(C/s+ni log ni ) where ni is the number of points
at the i-th site, and the total running time at the coordinator
is O(C).
Figure 2 visualizes the communication-round tradeoff.
Let t = dr/2e. We describe our tradeoff algorithm in Algorithm 2. The algorithm again starts with a local skyline
computation at each site. Similar to Algorithm 1, the rest
of the tradeoff algorithm still proceeds in rounds. The main
difference is that at each round, the parties (sites and the
coordinator) first jointly compute (1/d, 1/(2d))-quantiles to
partition the Euclidean plane to a set of at most d vertical
strips, and then instead of computing the (at most 2) points
with the global maximum x/y coordinates, the coordinator
computes for each non-empty strip the point with the maximum y-coordinate by collecting information from the sites
(Line 5-8); after that the parties use these points to compute new skyline points and prune each strip. We call the
combination of computing the quantiles and maximum ycoordinates, and finding new skyline points and performing
local pruning, one step of the computation. The algorithm
runs for (t − 1) steps, and after that the sites simply send
all the remaining points to the coordinator.

Algorithm 2 Communication-Round Tradeoff under Horizontal Partition
Input: Si is initialized as the point set held by Site i; r
(#communication-rounds) is a user-chosen parameter;
d is a parameter specified in the analysis.
Output: the global skyline
1: Site i computes its local skyline points and prunes the
other (dominated) points in Si
2: ` ← 0; t ← dr/2e
3: while (` ≤ t − 1) ∧ (∃i ∈ [s] s.t. Si 6= ∅) do
4:
All sites and the coordinator jointly compute
(1/d, 1/2d)-quantiles
according to the x-coordinates of
S
points in i∈[s] Si
. the quantile points naturally
partition the Euclidean plane to d strips
5:
for each i s.t. Si 6= ∅ do
6:
Site i, for each non-empty strip, sends the point
with the largest y-coordinate to the coordinator
7:
end for
8:
The coordinator, for each strip, finds the point with
the largest y-coordinate among points received from
sites; let Y denote the set of these points among all
strips
9:
The coordinator computes new skyline points from
Y and sends them to each site
10:
for each i s.t. Si 6= ∅ do
11:
Site i prunes Si by new global skyline points received from the coordinator
12:
end for
13:
`←`+1
14: end while
15: ∀i ∈ [s], Site i sends Si to the coordinator
16: The coordinator updates the global skyline using the
new points received from sites

We now show the correctness of Algorithm 2 and analyze
its costs. The high level intuition on the round efficiency of
Algorithm 2 is that at each round, the point with the maximum y-coordinate in each strip will either contribute to the
global skyline or help to prune all the points in that strip.
Compared with Algorithm 1, one can think that we are trying to prune the whole data set in parallel, that is, in each
strip of the plane. This will reduce the round complexity at
the cost of mildly increasing the total communication cost.
Correctness. The correctness of Algorithm 2 is straightforward: our skyline computation does not prune any point
that is not dominated by others. Indeed, up to the (t − 1)-th
step (or, (2t − 2)-th round), what Algorithm 2 does can be
summarized as “sites send candidate global skyline points
→ the coordinator computes new global skyline points from
these candidates → sites use new skyline points to prune
their local datasets”. At the (2t − 1)-th round, sites just
send all the remaining unpruned points to the coordinator
so that we will not miss any skyline points.
Communication cost. We count the communication cost
in two parts. The first part is the communication needed
at the first (t − 1) steps, and the second part is the total
number of remaining points at all sites after the (t − 1)-th
step, which will be sent to the coordinator all at once at the
final round.
We first analyze the cost of computing quantiles at each
step. We can compute (, /2)-quantiles using the following

folklore algorithm: the i-th site (for all i ∈ [s]) sends the
coordinator the exact /2-quantiles Qi of its local point set
Si . Using {Q1 , . . . , Qs }, the coordinator can answer quantile
queries as follows: Given a query rank β, it returns the
largest v satisfying
P
β − i∈[s] ranki (v) ≥ 0,
where ranki (v) = ni (v) · (/2 · |Si |), and ni (v) is the number
of /2-quantiles in Qi thatPis smaller than v. It is easy to
see that 0 ≤ β − v ≤ /2 · i∈[s] |Si |. The following lemma
summarizes the communication cost of this algorithm.
Lemma 1. There is an algorithm that computes (, /2)quantiles in the coordinator model using one round and O(s/)
communication.
Thus the communication used for quantile computation
can be bounded by O(sd) at each step. The rest communication at each step includes sending local maximums at
all strips and new skyline points, which can be bounded by
O(sd) we as well. To sum up the total communication in
the first part is bounded by O(sd(t − 1)).
The rest of the analysis is devoted to the second part, that
is, to bound the number of the remaining points after the
(t − 1)-th step.
We first assume that the output size k is known, and d
will be chosen as a function of k. We will then show how to
remove this assumption.
Let Y` ∈ [1, d] denote the number of new skyline points we
find at the `-th step. Observe that in each strip, if the point
with the largest y-coordinate is not a skyline point, then the
rest of the points in that strip cannot be skyline points and
thus are pruned. After the first step, there are at most Y1
strips having point and each strip has at most 2n/d points,
so there are at most
Y1 · 2n/d = 2nY1 /d
points left. After the second step, there are at most Y2 strips
having point and each strip has at most 2(2nY1 /d)/d points,
so there are at most
Y2 · 2 (2nY1 /d) /d = 4nY1 Y2 /d2

(Y1 + Y2 ≤ k)

points left. After the (t − 1)-th step, there are at most


Y
X
 t−1
t−1

Y` d
Y` ≤ k (1)
2 n
`∈[t−1]


≤ n

2k
(t − 1)d

`∈[t−1]

t−1
(2)

points left, where from (1) to (2) we have used the AM-GM
inequality and the equality holds when all Y` = k/(t − 1) (` =
1, . . . , t−1). We thus have at most n(2k/((t−1)d))t−1 points
left at sites after (t − 1)-th step, and the sites will send all of
them in the final (i.e., (2t − 1)-th) round. Adding two parts
together, the total communication cost is bounded by

t−1
2k
.
(3)
O(sd(t − 1)) + n
(t − 1)d
When
d=

2k
·
t−1



n(t − 1)
2sk

1/t
,

(4)

Expression (3) simplifies to be O(sk(t−1)/t (n/s)1/t ).

Y

Dealing with unknown k. We now show how to deal
with the case that we do not know k at the beginning. A
simple idea is to guess k as powers of 2 (i.e., 1, 2, 4, 8, . . .),
and
Pfor each guess, we run our algorithm, and report error
if
Y` > k at some point, in which case we double the
value of k and rerun the algorithm. The correctness of the
algorithm still holds. The round complexity, however, may
blow up by a factor of log k in the worst case. We will show
that there is a way to preserve the round complexity even
when we do not know k at the beginning.
The new idea is to guess k progressively, based on the
number of new skyline points found in the previous step.
More precisely, we set the guess of k at the `-th step, denoted
by k` , to be Y`−1 · (t − 1), for ` ≥ 2; and we set k1 = t − 1
to begin with. Now at the `-th step we use

1/t
n(t − 1)
2k`
·
(5)
d = d` =
t−1
2s
strips for the pruning. Note that (5) is very similar to (4),
where we have replaced the first k in (4) by k` and removed
the second k in (4).
Similar to (2), after (t − 1)-th step, there are at most
Y
2t−1 n
(Y` /d` )
`∈[t−1]

points left, and consequently the total communication cost
is bounded by
X
Y
s
d` + 2t−1 n
(Y` /d` ).
(6)
`∈[t−1]

`∈[t−1]

We now bound the two terms in (6) separately. We first
have
P

1/t
X
2s `∈[t−1] k`
n(t − 1)
·
s
d` =
(t − 1)
2s
`∈[t−1]


≤ 2sk ·

n(t − 1)
2s

1/t
.

(7)

where we have used the inequality


X
X
k` = (t − 1) 1 +
Y`  ≤ (t − 1)k.
`∈[t−1]

`∈[t−2]

For the second term, we have
2t−1 n

Y

(Y` /d` )

= n

`∈[t−1]

Y1 Y2 · · · Yt−1
Y1 Y2 · · · Yt−2



n(t − 1)
2s

t/(t−1)


1/t
n(t − 1)
2s
n(t − 1)
2s

1/t
n(t − 1)
2sk
.
(8)
(t − 1)
2s

= nYt−1 ·
≤

By (7) and (8), the total cost is bounded by O(sk(n/s)1/t ) =
O(sk(n/s)1/dr/2e ), as claimed.
Running time. The time cost at each site involves three
parts: the computation of the local skyline, the computation
of local quantiles, and the point prunings. Computing local
skyline again cost O(ni log ni ) where ni is the number of

y1
y3
y4

y2

Site 1

Site 2

Site 3

Site 4

X

Figure 3: Algorithm for Sorted Dataset
points at the i-th site. The cost of point prunings can again
be made linear in ni for the same reason as that in Algorithm 1. Now we analysis the time cost of computing the
local quantiles. Since points are sorted after the local skyline computation, computing (exact) local quantiles needs
O(d` ) time at the `-th step. Thus the total time is bounded
P
by `∈[t−1] d` = O(k(n/s)1/t ) = O(k(n/s)1/dr/2e ).
The running time at the coordinator also consists of three
parts: the computation of approximate global quantiles at
each step, the computation of new skyline points from the
first step to the (t − 1)-th step, and the computation of
skyline points (output) at the end. The observation is that
at each step, for each of the three tasks, the running at the
coordinator can be asymptotically bounded by the number
of points it receives from all sites in that step, and thus
the total running time at the coordinator is asymptotically
upper bounded by the total communication cost.

2.1.3

An Algorithm for Sorted Datasets

In this section we show that we can do much better if the
data points are partitioned to the s sites in a sorted order
with respect to the x-coordinate (or, the y-coordinate). In
other words, let x1 ≤ x2 ≤ . . . ≤ xs−1 be (s − 1) split
points, and let x0 = −∞ and xs = ∞. The i-th site gets all
points between (xi−1 , xi ]. See Figure 3 for an illustration.
As mentioned in the introduction, in the coordinator model
we cannot afford to repartition the dataset. Therefore the
algorithm presented in this section is only useful for settings
where the data has already been sorted among the sites.
Theorem 3. For n points in the 2-dimensional Euclidean
space partitioned among the s sites in the coordinator model
in the sorted manner according to their x-coordinates or ycoordinates, there exists an algorithm for computing the skyline that uses O(k + s) communication and 2 rounds, where
k is the output size, that is, the number of points in the skyline. The total running time at the i-th site is O(ni log ni )
where ni is the number of points at the i-th site, and that at
the coordinator is O(k + s).
We described our algorithm for sorted datasets in Algorithm 3. Let us explain in words. Same as before, each site
first does a local pruning and computes its local skyline. In
the first round, the i-th site sends the coordinator the point
which has the largest y-coordinate, denoted by yi . In the
second round, the coordinator for each i ∈ [s] computes the
value zi which is the maximum value among {yi+1 , . . . , ys },
and sends zi to the i-th site. The i-th site then prunes all
its local points with y-coordinate smaller than zi , and sends
the rest of its points to the coordinator.
We now show the correctness of this algorithm and analyze
its costs. The claim is that the points in Si with y-coordinate

Algorithm 3 Sorted Datasets under Horizontal Partition
Input: Si is initialized as the point set held by Site i
Output: the global skyline
1: Site i computes its local skyline points and discards the
other points in Si
2: Site i sends the point with the largest y-coordinate, denoted by yi , to the coordinator
3: The coordinator computes for ∀i ∈ [s], zi =
max{yi+1 , . . . , ys }, and sends zi to Site i
4: Site i prunes Si using zi , and sends the rest points to
the coordinator
5: The coordinator updates the global skyline using the
new points received from sites

Figure 4: Translating vector X10 = 1001100110 (m = 5) to
a staircase.

larger than zi , denoted by Pi , must on the global skyline.
Indeed, points in Pi can not be dominated by any point in
S1 , . . . , Si−1 since all points in Si have x-coordinates larger
than those points in S1 , . . . , Si−1 . On the other hand, points
in Pi cannot be dominated by any point in Si+1 , ..., Ss since
all points in Pi have y-coordinates larger than the those
points in Si+1 , . . . , Ss . The communication of the algorithm
includes sending yi and zi (costs 2s) plus sending skyline
points (costs k). The running time at each site is dominated
by the local skyline computation, and the time cost at the
coordinator is clearly O(k + s) (O(s) for the first round and
O(k) for the second round).

2.2
2.2.1

Lower Bounds
Infinite Rounds

We prove a lower bound for the infinite-round case by
a reduction from a communication problem called s-DISJ.
The lower bound matches the upper bound by Algorithm 1
up to a logarithmic factor which counts the number of bits
used to represent a point in the Euclidean plane.
In s-DISJ, each of the s sites gets an m-bit vector. Let
Xi = (Xi1 , . . . , Xim ) be the vector the the i-th site gets.
We can view the whole input as an s × m matrix X with
Xi (i ∈ [s]) as rows. The s-DISJ problem is defined as
follows:

 1, if there exists a j ∈ [m] s.t.
s-DISJ(X1 , . . . , Xs ) =
∀i ∈ [s], Xij = 1,

0, otherwise.
Lemma 2 ([5]). Any randomized algorithm for s-DISJ
that succeeds with probability 0.51 has communication cost
Ω(sm). The lower bound holds even when we allow an infinite number of communication rounds.
The Reduction. Given the m-bit vector Xi for s-DISJ, the
i-th site first converts it to a 2m-bit vector Xi0 as follows:
each 0 bit will be converted to 01, and each 1 bit will be
converted to 10. For example, when m = 5 and Xi = 10101,
Xi0 should be 1001100110. The next step is to convert Xi0
to a staircase. This step is illustrated in Figure 4. We can
“embed” the staircase into an m × m grid. The staircase
starts from the top-left point of the grid, and grows in 2m
steps. In the `-th step, if the `-th coordinate of Xi0 is 0,
then the staircase grows one step horizontally rightwards;
otherwise if the `-th coordinate is 1, then the staircase grows
one step vertically downwards.

Figure 5: The solid red skyline corresponds to the case that
s-DISJ(X1 , . . . , Xs ) = 0, and the dash blue skyline corresponds to the case that s-DISJ(X1 , . . . , Xs ) = 1.

The observation is that if we create s staircases using
X10 , . . . , Xs0 , then the skyline of the union of these s staircases is closely related to the value of s-DISJ(X1 , . . . , Xs ):
If s-DISJ(X1 , . . . , Xs ) = 0, then the skyline will be in the
form of the red curve in Figure 5; otherwise, the skyline will
be different from the red curve (e.g., be the blue curve in
Figure 5 if the 3rd coordinates of X1 , . . . , Xs are all 1). This
is because for each column j ∈ [m] in the grid, as long as
there is one i ∈ [s] such that the j-th coordinate of Xi is 0,
or the (2j − 1)-th and (2j)-th coordinates of Xi0 is 01, the
skyline within the j-th column of the grid will be like “q”;
otherwise if for all i ∈ [s] the j-th coordinate of Xi is 0, then
the skyline within the j-th column of the grid will be like
“x”. The other direction also holds, that is, if the skyline is
in the form of the red curve, then s-DISJ(X1 , . . . , Xs ) = 0;
otherwise, s-DISJ(X1 , . . . , Xs ) = 1.
When the size of the skyline is k, we set m = k according
to our reduction, and obtain the following theorem.
Theorem 4. Any randomized protocol for computing skyline in the coordinator model with horizontal partition that
succeeds with probability 0.51 has communication cost Ω(sk)
bits, where k is number of points in the skyline. The lower
bound holds even when we allow an infinite number of communication rounds.

2.2.2

One Round

We now prove an Ω(n) communication lower bound for the
case that the algorithm needs to finish in one round. This
proof is simpler than the infinite-round case – we only need

two sites to participate in the game. We assign Site 1 an
m-bit vector u, which can be converted to a staircase in the
m × m grid just like the infinite-round case, and assign Site
2 one bit v, which is translated to the upper-right conner
point of the grid if v = 1 and the lower-left conner point of
the grid if v = 0. We have the following simple observation,
which holds because if we change one bit of the vector m
from 0 to 1, we will change a “q” to “x” in the staircase, and
thus change the skyline; same for replacing a bit 1 to 0.
Observation 1. If the coordinator needs to compute the
global skyline, and v = 0, then it needs to learn the vector u
exactly.
We immediately have the following lemma.
Lemma 3. Any one round randomized algorithm for the
coordinator to learn u exactly with probability 0.51 has communication cost Ω(m).
Note that when v = 1, the skyline only consists of a single
point in the upper right conner. Therefore the output size
k is not directly related to the value m; we thus can set
m = Ω(n).
Theorem 5. Any one round randomized algorithm for
computing skyline in the coordinator model with horizontal
partition that succeeds with probability 0.51 has communication cost Ω(n) bits, where n is the total number of points
held by all sites.

3.

VERTICAL PARTITION

In the vertical partition, each site holds a single coordinate
of all the data points. Since we consider points in the 2dimensional Euclidean space in this paper, we only have
two sites, named Alice and Bob. We store the ID (key) of
each point on both sites. More precisely, Alice has a set
of tuples {(xp1 , IDp1 ), (xp2 , IDp2 ), . . .}, where xpi is the xcoordinate of point pi and IDpi is the ID of pi ; and Bob
has a set of tuples {(IDq1 , yq1 ), (IDq2 , yq2 ), . . .}, where yqi is
the y-coordinate of point qi . We can join the two tables to
recover the information of all points.

3.1

A Strong Lower Bound

As mentioned in the introduction, in the vertical partition case there is a strong communication lower bound,
which states that in the worst case sites have to send almost
everything to the coordinator. We prove the lower bound
by a reduction from a classical problem in communication
complexity called two-party set-disjointness (denoted by 2DISJ). In the 2-DISJ, we have two parties Alice and Bob.
Alice holds a set of numbers A ⊆ [n], and Bob holds a set
of numbers B ⊆ [n], and they want to jointly compute

1, A ∩ B 6= ∅,
2-DISJ(A, B) =
0, otherwise.
Fact 1 ([3]). Any randomized protocol for 2-DISJ that
succeeds with probability 0.51 has communication cost Ω(n).
The Reduction. Alice uses her input A to create the xcoordinates of the n points as follows: for each a ∈ A, she
creates a point (2, a) where 2 is the x-coordinate and a is the
ID of the point; and for each a ∈ [n]\A, she creates a point

(1, a). Bob uses his input B to create the y-coordinates of
the n points in a similar way: for each b ∈ B, he creates a
point (b, 2) where 2 is the y-coordinate and b is the ID of
the point; and for each b ∈ [n]\B, he creates a point (b, 1).
It is easy to see that if A∩B 6= ∅, then there is at least one
point in the (2, 2) position, which will be the only point in
the skyline; otherwise, the skyline will consist of two points
(1, 2) and (2, 1). By Fact 1 we have
Theorem 6. Any randomized algorithm for computing skyline in the distributed model with vertical partition that succeeds with probability 0.51 has communication cost Ω(n), regardless how many rounds the algorithm uses.

3.2

A Simple Heuristic

Given the strong lower bound result in Section 3.1, we propose in this section a heuristic which is communication efficient on real-world datasets. Our algorithm can be thought
as a batched pruning version of the Threshold-Algorithm
based approach [2, 12], but has been tailored for boundedround distributed computation. We call our heuristic interactive pruning; the pseudocode is described in Algorithm 4.
We now explain our algorithm in words. Let r be the
round budget and ρ be the parameter denoting the number
of groups we use for the algorithm. We say a point p is
recovered at the coordinator if both the x and y coordinates
of p are known to the coordinator.
Alice and Bob first sort decreasingly all points according to the x-coordinates and y-coordinates respectively, and
then partition the points to ρ groups, denoted by Gx1 , . . . , Gxρ
and Gy1 , . . . , Gyρ respectively. The coordinator tries to learn
both coordinates of the points that possibly lie in the skyline progressively. It maintains four variables fx , fy , lx , ly :
fx and fy stand for the indices of the next groups Alice and
Bob will send to the coordinator respectively; and groups
with indices at least lx and ly at Alice and Bob respectively have already been pruned. Observe that if fx ≥ lx
or fy ≥ ly , then the coordinator must have recovered all
the skyline points, and thus the algorithm can terminate.
Based on this fact, the coordinator always chooses the site
with the smaller gap value lx − fx or ly − fy , and asks for
the information of its next group Gxfx or Gyfy .
Algorithm 4 proceeds in three stages. The first stage consists of two rounds (Line 3 to 5). The goal of the first stage
is to recover the first groups Gx1 and Gy1 at Alice and Bob,
and update the variables lx and ly to determine the next
group to recover. The second stage consists of b(r − 4)/2c
steps each of which consisting of two rounds (Line 6 to 10).
The goal of the second stage is to recover points progressively
from the site which has a smaller gap value. The algorithm
will stop early if at some step all points have been either
pruned or recovered at a site. The goal of the third stage is
to recover all groups that are still not recovered or pruned
after the first two stages. This is done at the coordinator
by first asking the site with the smaller gap value to get the
IDs of points in these groups together with one of the two
coordinates, and then contacting the other site for the other
coordinates of these points. We include a running example
for Algorithm 4 in Appendix A.
The correctness of the algorithm is straightforward since
when our algorithm stops, all points at one site are either
recovered or pruned. The local running time at each site
is dominated by the initial sorting which is O(n log n), and

Algorithm 4 Interactive Pruning under Vertical Partition
Input: S1 is the set of the x-coordinates of points held
by Alice, and S2 is the set of the y-coordinates of points
held by Bob. ρ (number of groups) and r (round budget)
are two user-chosen parameters.
Output: the global skyline
1: Alice sorts S1 decreasingly and then partitions it to ρ
groups of equal size, denoted by Gx = {Gx1 , . . . , Gxρ }.
Bob does the same thing on S2 and gets groups Gy =
{Gy1 , . . . , Gyρ }. Alice and Bob send the splitting coordinates of the group partitions to the coordinator. Given
a point p, let gx (p) be the index of the group in Gx that
contains p, and gy (p) be the index of the group in Gy
that contains p
2: The coordinator maintains a set of points R denoting
the recovered points, and four variables: fx , fy , lx , ly .
3: The coordinator communicates with Alice and Bob to
learn both the x-coordinates and y-coordinates of points
in Gy1 and Gx1 , adds them to R, and then updates
lx ← min{gx (p) | p ∈ Gy1 } + 1 and ly ← min{gy (p) | p ∈
Gx1 } + 1
4: The coordinator sets fx ← 2, fy ← 2
5: j ← 1
. index of steps; one step uses two rounds
6: while (2j ≤ r − 4) ∧ (lx > fx ) ∧ (ly > fy ) do
7:
If lx − fx ≤ ly − fy , the coordinator requests group
Gxfx from Alice and updates fx ← fx +1, else it requests
Gyfy from Bob and updates fy ← fy + 1
8:
The coordinator recovers and adds points in Gxfx (or
Gyfy ) to R, and updates ly ← min{ly , min{gy (p) | p ∈
Gxfx } + 1} (or lx ← min{lx , min{gx (p) | p ∈ Gyfy } + 1})
9:
j ←j+1
10: end while
11: if (lx > fx ) ∧ (ly > fy ) then
12:
The coordinator compares lx −fx and ly −fy ; w.l.o.g.,
assume lx − fx is smaller. The coordinator sends fx and
lx to Alice. Alice then sends the x-coordinates and IDs
of points (denoted by P ) in Gxfx , . . . , Gx(lx −1) to the
coordinator.
13:
The coordinator sends the IDs of points in P to Bob.
Bob then sends the y-coordinates of points in P to the
coordinator. The coordinator adds points in P to R
14: end if
15: The coordinator computes and outputs the skyline of R

score of each point which is the sum of the differences between each of its coordinates and the coordinate of the last
point recovered by the sorted access at the respective site.
PDS uses linear regression to estimate the rank of each point,
and the point with the lowest rank is considered to be the
most probable terminating point. In our algorithm, instead
of looking for the most probable terminating point, we focus
on the number of unrecovered and unpruned groups remaining at each site. We choose to request a new group of points
from the site with the smaller number of remaining groups,
with the purpose of terminating the algorithm earlier.
It is well-known that the Threshold-Algorithm [7] is instance optimal in terms of number of points probed, and thus
if we only measure the number of points recovered at the coordinator in the process, our batched pruning approach has
no advantage compared with the individual point prunings
in BDS, IDS and PDS. However, as we shall see in the experiments (Section 4), batched pruning can not only significantly
reduce the round cost, but also bring down the overall communication cost in some cases. This is because in each step
the coordinator needs to send a message to request points
from the sites in the sorted access, and consequently the
round cost will influence the communication cost as well.

4.

The Datasets. We use both synthetic and real-world datasets.
We generated three synthetic datasets following the standard literature [4]. The data partition among the sites will
be described in Section 4.1 (horizontal partition) and Section 4.2 (vertical partition) respectively.
• INDI(independent): We generate 20 million points. For
each point we generate each of its coordinates independently uniformly at random from [0, 1]
• CORR(correlated): We select 200 thousand lines (denoted by L1 ) perpendicular to the line from (0, 0) to
(1, 1), where the intersections follow the standard normal distribution. Next, for each line in L1 we pick 100
points also following the standard normal distribution.
We have 20 million points in total.

the time cost at the coordinator is dominated by the final
skyline computation which is also O(n log n).
We comment that ρ is a parameter that we need to choose
at the beginning of the algorithm; we will discuss how to
choose ρ in the experiments in Section 4.
A comparison to previous algorithms. Our algorithm,
the BDS algorithm and its improvement the IDS algorithm
proposed in [2], and the PDS algorithm proposed [12] are all
based on the Threshold-Algorithm (TA) [7]. A clear difference is that BDS, IDS and PDS recover one point in each step
at the coordinator, while we recover at least one group of
points in each step which helps to significantly reduce the
round cost. The second major difference is that to improve
the basic TA-base algorithm BDS, both IDS and PDS share
the idea of estimating the most probable terminating point,
and then using it to decide which site to access next. IDS
finds the most probable terminating point by calculating the

EXPERIMENTS

In this section we present the experimental studies of our
proposed algorithms. We have implemented all algorithms
in C++. All experiments were conducted on a laptop with
Inter Core i7 running Windows 7 with 4GB memory.

• ANTI(anti-correlated): We select 200 thousand lines
(denoted by L2 ) perpendicular to the line from (0, 1) to
(1, 0), where the intersections follow the standard normal distribution. Next, for each line in L2 we pick 100
points also following the standard normal distribution.
We have 20 million points in total.
We make use of the following real-world datasets.
• Airline: this dataset contains 3 million the airline
itineraries and prices between 30 U.S. major cities in
2015 first quarter.2 We choose (minus) fare and (minus) fare-per-mile as the two attributes in x and y
coordinates. The skyline points are considered to be
economic flights.
2

Available at http://www.transtats.bts.gov.

• Household [11]: this dataset contains 2 million household electric power consumption records gathered between December 2006 and November 2010. We choose
voltage and intensity as the two attributes in x and y
coordinates. The skyline points represent those households that are recommended to pay attention to the
energy efficiency.

Data Partition. For the three synthetic datasets, we partition points randomly to 20 sites. For Airline, we partition
the data records in the same city to the same site; we thus
have 30 sites. For Household, we partition the data collected
in every two consecutive months to the same site; 20 sites in
total. For Covertype, we just randomly partition the data
records to 20 sites.

• Covertype [11]: this dataset contains 500 thousand
natural statistics from four wilderness areas located in
the Roosevelt National Forest of northern Colorado.
We choose elevation and slope as the two attributes
in x and y coordinates. The skyline points represent
areas that may have interesting geological behaviors.

Results and Discussions. Figure 6 and Figure 7 show the
communication and round costs of the five tested algorithms
on the three synthetic datasets and three real-world datasets
mentioned above.
We observed that by using three rounds, the communication cost of Tradeoff is 25%-44% of that of Naive on
synthetic datasets and 22%-31% on real-world datasets, and
is also close to Optimal which uses more rounds. We noticed that the advantage of Tradeoff against Naive is larger
in real-world datasets (even of smaller sizes) than synthetic
ones. This is because it is more likely in real-world datasets
that a point in one site dominates most of the local skyline
points in another site. We observe that in Household, by using 5 rounds Tradeoff needs even less communication than
Optimal. This is possible since Optimal is just asymptotically optimal in the worst case.
The communication cost of AGiDS, which uses two rounds,
is similar to Naive on Airline and Household and even
worse on INDI, CORR, and Covertype, and is consequently
much worse than Tradeoff and Optimal. FDS uses the largest
amount of rounds (even more than Optimal), but its communication is worse than both Tradeoff and Optimal on all
synthetic and real-world datasets.
Figure 8 and Figure 9 show the running time of the tested
algorithms (excluding the cost the common local skyline
computation at the beginning) on synthetic and real-world
datasets respectively.3 Generally speaking the running time
of all algorithms are similar. On the ANTI dataset, the running time of Optimal and FDS are clearly worse than others.
This is because they need many more rounds than other
algorithms on ANTI.

4.1

Horizontal Partition

Algorithms. We compare the following algorithms in the
case of horizontal partition.
• Naive: the single round algorithm in which each site
computes and sends its local skyline to the coordinator
for a merge.
• Optimal: Algorithm 1 in Section 2.1.1. The algorithm
that achieves the optimal communication cost.
• Tradeoff: Algorithm 2 in Section 2.1.2. The algorithm
that gives a smooth communication-round tradeoff.
• AGiDS: We use the AGiDS algorithm proposed in [15] as
a comparison. To make AGiDS fit in our model, we use
the following version of the original algorithm: At the
beginning, the coordinator and sites share the information of a grid in which each cell represents a range
in the x/y-axes (equal width partition). In the first
round (the planing phase), sites send the information
of non-empty cells to the coordinator. In the second
round (the execution phase), the coordinator finds the
cells that may contribute to global skyline and sends
the information to sites, and then sites send points in
these cells to the coordinator. Finally the coordinator
computes the skyline of received points as the output.
We comment that this algorithm is also very similar
to the relaxed skyline algorithm proposed in [1]. We
choose the grid to be 20 × 20 (total 400 cells) in our
experiments which works the best under our settings.
• FDS: We use the FDS algorithm proposed in [20] as a
comparison. The original algorithm proceeds in iterations. To make it fit in our model, we use three rounds
for each iteration: In the first round (the voluntary
phase), each site sends the top κ points with the largest
scores (x + y) to the coordinator. In the second round
(the compulsory and computation phase), the coordinator calculates the minimum score (denoted by Fmin )
from received points and sends it to each site. Each site
then sends all its local points that have larger scores
than Fmin to the coordinator. The coordinator updates
the global skyline with points received in the first two
rounds. In the third round (the feedback phase), the
coordinator calculates and sends each site a feedback,
which consists of points that are guaranteed to dominate at least ` points in that site. And then each site
does a local pruning. κ and ` are two parameters in
FDS; we choose the optimal values κ = 1 and ` = 1 as
reported in [20].

Summary. Tradeoff achieves noticeable communication
cost reductions than AGiDS and Naive by using one or two
more rounds; its performance is very close to the theoretical
optimal algorithm Optimal in the communication cost but
is much more efficient in rounds. On the other hand, AGiDS
does not have an advantage against Naive in communication
but uses one more round, and the performance of FDS is
clearly dominated by Tradeoff and Optimal. All algorithms
have similar time costs since the computation of the local
skylines dominates the other costs.

4.2

Vertical Partition

We compare the following algorithms in the vertical partition case.
• Prune: Algorithm 4 in Section 3.2.
• BDS and IDS: We use the BDS and IDS algorithms proposed in [2] as comparisons. See Section 3.2 for a brief
description of these two algorithms.
3
The local skyline computation takes about 6 seconds on all
the three synthetic datasets and 1.1, 0.6, 0.2 seconds on the
Airline, Household and Covertype respectively. This cost
in fact dominates the other time costs.

0.008

0.000

0.003
0.002

0.002

1

2

3

4

Round

5

44

158

0.000

0.006

0.004

0.004

0.005

0.007

0.005

0.006

0.010

Naive
AGiDS
Trade-off
Optimal
FDS

0.008

Communication Cost(%)

Communication Cost(%)

0.015

Naive
AGiDS
Trade-off
Optimal
FDS

0.010

Communication Cost(%)

Naive
AGiDS
Trade-off
Optimal
FDS

0.020

0.001

1

2

3

ANTI

4

5

Round

13

22

0.000

1

2

3

INDI

4

Round

5

8

34

CORR

Figure 6: Communication and round costs on synthetic datasets under horizontal partition

0.04

0.07
0.06
0.05
0.04

0.03

0.05

0.02

0.01
0.00

0.01

1

2

3

4

Round

Airline

5

17

50

0.00

0.15

0.10

0.03

0.02

Naive
AGiDS
Trade-off
Optimal
FDS

0.20

Communication Cost(%)

Communication Cost(%)

0.05

Naive
AGiDS
Trade-off
Optimal
FDS

0.08

Communication Cost(%)

Naive
AGiDS
Trade-off
Optimal
FDS

0.06

1

2

3

4

5

Round

Household

19

50

0.00

1

2

3

4

Round

5

14

28

Covertype

Figure 7: Communication and round costs on real-world datasets under horizontal partition

Figure 8: Running time on synthetic datasets under horizontal partition (in Tradeoff we use 5 rounds). The time for
local skyline computation at the beginning is not included.
• PDS: We use the PDS algorithm proposed in [12] as a
comparison. See Section 3.2 for a brief description of
this algorithm.
Figure 10 and Figure 11 show the communication and
round costs of the four tested algorithms on the three synthetic datasets and three real-world datasets mentioned above.
We observed that by using at most eight rounds, the communication cost of Prune is similar or even smaller than that
of BDS, IDS and PDS, which use significantly more rounds. It
is surprising to see that PDS is even worse then BDS in most
cases; the original paper [12] did not make this compari-

Figure 9: Running time on real-world datasets under horizontal partition (in Tradeoff we use 5 rounds). The time for
local skyline computation at the beginning is not included.

son on points in the 2D Euclidean space. One reason that
Prune can achieve better communication costs is that IDS
and PDS have significantly larger round complexities, and at
every two rounds the coordinator needs to send a message
to a site to request for the next point, which can be considered as an overhead of the algorithms in the distributed
setting. We also observe that Prune recovers similar number
of points as BDS, IDS, and PDS; see Table 1 for the details.
In Figure 10 and Figure 11 we have set ρ to be 1000, 10000,
100000 for three synthetic datasets ANTI, INDI and CORR, and
500 for all three real-world datasets. These values are not

Communication Cost (%)

3.0
2.5

Prune
IDS
BDS
PDS

0.4

1.5

0.03
0.02

0.1

0.5
4

6

8 185890

Round

201354

0.0

242442

0.06

0.04

0.2

1.0

Prune
IDS
PDS
BDS

0.07

0.05

0.3

2.0

0.0

0.08

0.5

Communication Cost (%)

Prune
IDS
BDS
PDS

Communication Cost (%)

3.5

0.01

4

6

8 25828

Round

ANTI

28196

34210

0.00

4

6

INDI

8

Round

1650

1854

2204

CORR

Communication Cost (%)

1.5
1.0
0.5
0.0

4

6

8

Round

9740

11022

12682

Prune
IDS
BDS
PDS

15

10

5

0

4

Airline

6

8 80059

Round

Household

96746

105306

Prune
IDS
BDS
PDS

7

Communication Cost (%)

Prune
IDS
BDS
PDS

2.0

Communication Cost (%)

Figure 10: Communication and round costs on synthetic datasets under vertical partition; for Prune we use parameter
ρ = 1000, 10000, 100000 for ANTI, INDI, CORR datasets respectively)

6
5
4
3
2
1
0

4

6

8

Round

9072

12094

12840

Covertype

Figure 11: Communication and round costs on real-world datasets under vertical partition; for Prune we use parameter
ρ = 500 for all Airline, Household, Covertype datasets)

ANTI
INDI
CORR
Airline
Household
Covertype

Prune
136094
13609
855
6776
52407
5258

IDS
92945
12914
825
4870
40029
4536

BDS
100677
14098
1102
5511
48373
6047

PDS
121221
17105
927
6341
52653
6420

Table 1: Number of recovered points at the coordinator. In
Prune, ρ is chosen to be 1000, 10000, 100000 for ANTI, INDI
and CORR respectively, and 500 for Airline, Household and
Covertype; the round budget r is set to be 8.

chosen optimally for each dataset, but follow some general
rules we have concluded from another set of experiments,
which we discuss next.
Figure 12 and Figure 13 show how the communication cost
changes when varying ρ. We observe that for a fixed round
budget, the communication cost curves generally obey a “U”
shape: the cost is very large when ρ is very small; this is
because the group size is too large so many recovered points
are wasted in the first few rounds. The cost then deceases
dramatically as ρ increases, becomes stable for a while, and
then increases again. We also observe that the stable range
of ρ becomes larger when the round budget r becomes larger,
which makes the choice of a good ρ more flexible. While the
best ρ inherently depends on the distribution of the dataset,

the lesson we have learned from Figure 12 and Figure 13 is
that ρ should be small (e.g., 1000) if the data distribution
is close to ANTI, large (i.e., 100000) if the distribution is
close to CORR, and medium (i.e., 10000) if the distribution is
close to INDI. It is reasonable to believe that most real-world
datasets are on the ANTI end, since an item which is strong
on one attribute may be weak on the other (think about
the price and location of hotels). Our experiments on three
real-world datasets Airline, Householdand Covertype show
that ρ = 500 can be a good default choice in practice.
Figure 14 and Figure 15 show the time costs of tested
algorithms on synthetic and real-world datasets respectively.
We do not take into account the initial sorting time which is
common to all algorithms.4 Generally speaking, the running
times of all algorithms are similar. This is because all of the
three algorithms are based on the TA approach. PDS has
the worst time performance in most cases because it needs
to recover the largest number of points and uses the most
number of rounds.
Summary. To conclude, Prune achieves a significant reduction on the round costs (3-4 orders of magnitude) while
preserves communication costs compared with IDS, which is
the best among the three existing algorithms. The running
times of all the tested algorithms are similar.
4

The sorting time is about 5 seconds on all the three synthetic datasets, and 0.9, 0.5, 0.15 seconds on Airline,
Household and Covertype.

0.65

3
Prune (r=4)
Prune (r=6)
Prune (r=8)

0.12
Prune (r=4)
Prune (r=6)
Prune (r=8)

0.6

2.2
2
1.8
1.6

Communication Cost(%)

2.4

0.5
0.45
0.4
0.35
0.3
0.25

1.4

Prune (r=4)
Prune (r=6)
Prune (r=8)

0.1

0.55

2.6

Communication Cost(%)

Communication Cost(%)

2.8

0.08

0.06

0.04

0.02

0.2

1.2
200

500

1000

1500

2000

0.15
0.1

0.5

1

Parameter ρ

1.5

2

2.5

3

Parameter ρ

ANTI

0
0.5

3.5

2

4

6

8

10

12

Parameter ρ

4

x 10

4

x 10

CORR

INDI

Figure 12: Communication cost versus parameter ρ on synthetic dataset under vertical partition
3.5

2

1.5

22
20
18
16
14
12

6
5.5
5
4.5
4
3.5
3

10

1

Prune (r=4)
Prune (r=6)
Prune (r=8)

7
6.5

Communication Cost(%)

2.5

Prune (r=4)
Prune (r=6)
Prune (r=8)

24

Communication Cost(%)

3

Communication Cost(%)

7.5

26
Prune (r=4)
Prune (r=6)
Prune (r=8)

2.5
8
200

1000

2000

3000

4000

Parameter ρ

Airline

5000

6000

25

200

400

600

800

2
100

Parameter ρ

500

1000

1500

2000

2500

Parameter ρ

Covertype

Household

Figure 13: Communication cost versus parameter ρ on synthetic dataset under vertical partition

Figure 14: Running time on synthetic datasets under
vertical partition; for Prune we use parameter ρ =
1000, 10000, 100000 for ANTI, INDI, CORR datasets respectively, and r = 8 rounds). The time for local skyline computation at the beginning is not included.

Figure 15: Running time on real-world datasets under vertical partition; for Prune we use parameter ρ = 500 for all Airline, Household, Covertype datasets, and r = 8 rounds).
The time for local skyline computation at the beginning is
not included.

5.

and/or round cost. For vertical partition, we first show a
strong lower bound, and then give a practical heuristic. Our
heuristic significantly outperforms existing ones in the round
cost, while achieves similar or better communication cost.
Further work includes designing algorithms for points in the
higher dimensional Euclidean spaces for both horizontal and
vertical data partitions.

CONCLUSION

In this paper we propose a set of algorithms for computing skylines on distributed data. We consider both horizontal and vertical data partitions. For horizontal partition
we give an algorithm that achieves the optimal communication cost. We also propose an algorithm with a smooth
communication-round tradeoff. We show experimentally that
our algorithms (with theoretical guarantees) significantly
outperform existing heuristics in the communication cost

6.

REFERENCES

Gx1
fx

Gx2

fy

Gy2

fx

Gx1

Gy1

Gx2

Gy2

fx

Gx1

Gy1

Gx2

Gy2

Gx3

Gy3

Gx3

Gy3

Gx3

Gx4

Gy4

Gx4

Gy4

Gx5

Gy5

Gx5

Gy5

Gx5

Gy5

Gx6

Gy6

Gx6

Gy6

Gx6

Gy6

Gy7

Gx7

Gy8

Gx8

Gx7
lx

Gy1

ly

Gx8

Gy7
Gy8

Round = 1, 2

lx

Gx7

fy

ly

Gx8

Gy3

Round = 3, 4

lx

Gx4

fy

ly

Gy4

Gy7
Gy8

Round = 5, 6

Figure 16: A running example of Algorithm 4, with parameters r = 8 and ρ = 8.

[1] F. N. Afrati, P. Koutris, D. Suciu, and J. D. Ullman.
Parallel skyline queries. Theory Comput. Syst.,
57(4):1008–1037, 2015.
[2] W. Balke, U. Güntzer, and J. X. Zheng. Efficient
distributed skylining for web information systems. In
EDBT, pages 256–273, 2004.
[3] Z. Bar-Yossef, T. S. Jayram, R. Kumar, and
D. Sivakumar. An information statistics approach to
data stream and communication complexity. J.
Comput. Syst. Sci., 68(4):702–732, 2004.
[4] S. Börzsönyi, D. Kossmann, and K. Stocker. The
skyline operator. In ICDE, pages 421–430, 2001.
[5] M. Braverman, F. Ellen, R. Oshman, T. Pitassi, and
V. Vaikuntanathan. A tight bound for set disjointness
in the message-passing model. In FOCS, pages
668–677, 2013.
[6] J. Chomicki, P. Ciaccia, and N. Meneghetti. Skyline
queries, front and back. SIGMOD Record, 42(3):6–18,
2013.
[7] R. Fagin, A. Lotem, and M. Naor. Optimal
aggregation algorithms for middleware. J. Comput.
Syst. Sci., 66(4):614–656, 2003.
[8] K. Hose and A. Vlachou. A survey of skyline
processing in highly distributed environments. VLDB
J., 21(3):359–384, 2012.
[9] H. Köhler, J. Yang, and X. Zhou. Efficient parallel
skyline processing using hyperplane projections. In
SIGMOD, pages 85–96, 2011.
[10] H. T. Kung, F. Luccio, and F. P. Preparata. On
finding the maxima of a set of vectors. J. ACM,
22(4):469–476, 1975.
[11] M. Lichman. UCI machine learning repository, 2013.
[12] E. Lo, K. Y. Yip, K. Lin, and D. W. Cheung.
Progressive skylining over web-accessible databases.
Data Knowl. Eng., 57(2):122–147, 2006.
[13] K. Mullesgaard, J. L. Pederseny, H. Lu, and Y. Zhou.
Efficient skyline computation in mapreduce. In EDBT,
pages 37–48, 2014.
[14] D. Pertesis and C. Doulkeridis. Efficient skyline query
processing in spatialhadoop. Inf. Syst., 54:325–335,
2015.
[15] J. B. Rocha-Junior, A. Vlachou, C. Doulkeridis, and
K. Nørvåg. Agids: A grid-based strategy for

[16]

[17]

[18]

[19]

[20]

distributed skyline query processing. In Data
Management in Grid and Peer-to-Peer Systems,
Second International Conference, pages 12–23, 2009.
G. Trimponias, I. Bartolini, D. Papadias, and
Y. Yang. Skyline processing on distributed vertical
decompositions. IEEE Trans. Knowl. Data Eng.,
25(4):850–862, 2013.
A. Vlachou, C. Doulkeridis, and Y. Kotidis.
Angle-based space partitioning for efficient parallel
skyline computation. In SIGMOD, pages 227–238,
2008.
S. Wang, B. C. Ooi, A. K. H. Tung, and L. Xu.
Efficient skyline query processing on peer-to-peer
networks. In ICDE, pages 1126–1135, 2007.
P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal,
and A. El Abbadi. Parallelizing skyline queries for
scalable distribution. In EDBT, pages 112–130, 2006.
L. Zhu, Y. Tao, and S. Zhou. Distributed skyline
retrieval with low bandwidth consumption. IEEE
Trans. Knowl. Data Eng., 21(3):384–400, 2009.

APPENDIX
A.

A RUNNING EXAMPLE FOR THE INTERACTIVE PRUNING ALGORITHM

Figure 16 shows a running example of Algorithm 4 with
parameters r = 8 and ρ = 8. In the first round, Alice sends
Gx1 and Bob sends Gy1 to the coordinator. In the second
round, the coordinator sends the IDs of points in Gx1 and
Gy1 to Bob and Alice respectively, and then Bob and Alice
send the y-coordinates and x-coordinates of points in Gx1
and Gy1 respectively to the coordinator. The coordinator
recovers the points in Gx1 and Gy1 and adds them to R
(the set of candidate skyline points), and updates lx = 8,
ly = 7, and fx = fy = 2. In the third and fourth rounds,
the coordinator chooses to recover points in Gy2 because
ly − fy < lx − fx , and then updates lx = 7. In the fifth and
sixth rounds, the coordinator chooses to recovers points in
Gy3 because ly − fy < lx − fx , and then updates lx = 4.
In the last two rounds, the coordinator asks Alice for the
information of the points in the remaining groups Gx2 and
Gx3 (i.e., the groups that have not been recovered or pruned)
since lx − fx < ly − fy .

