Shooting Stars in the Sky:
An Online Algorithm for Skyline Queries
Donald Kossmann
Frank Ramsak
Steffen Rost
Technische Universitiit Miinchen
Orleansstr. 34
81667 Munich
Germany
{kossmann, rost}~in.tum.de, frank.ramsak~forwiss.de
Abstract
Skyline queries ask for a set of
interesting
points
from a potentially large set of data
points. If we are traveling, for instance, a
restaurant might be interesting if there is no
other restaurant which is nearer, cheaper,
and has better food. Skyline queries retrieve
all such interesting restaurants so that the
user can choose the most promising one. In
this paper, we present a new
online algo-
rithm that computes the Skyline. Unlike
most existing algorithms that compute the
Skyline in a batch, this algorithm returns
the first results immediately, produces more
and more results continuously, and allows
the user to give preferences during the run-
ning time of the algorithm so that the user
can control what kind of results are pro-
duced next (e.g., rather cheap or rather near
restaurants).
1 Introduction
1.1 Skyline Queries
Recently, there has been a growing interest in so-
called Skyline queries [BKS01, TEO01]. The Skyline
of a set of points is defined as those points that are
not dominated by any other point. A point domi-
nates another point if it is as good or better in all
dimensions and better in at least one dimension.
Permission to copy without fee all or part of this material is
granted provided that the copies are not made or distributed
for direct commercial advantage, the VLDB copyright notice
and the title of the publication and its date appear, and no-
tice is given that copying is by permission of the Very Large
Data Base Endowment. To copy otherwise, or to republish,
requires a fee and/or special permission from the Endowment.
Proceedings of the 28th VLDB Conference,
Hong Kong, China, 2002
I
i
1.0 -
j
0.5 - ---~......~~
0.0 l 1 I l
50 100 150 200
Pr~e [t;]
Figure 1: Skyline of hotels in Nassau (Bahamas)
The classic example is shown in Figure 1. The
figure shows the Skyline of hotels in Nassau (Ba-
hamas) which are supposed to be cheap and close
to the beach. The bold points (which are connected
in the graph) represent those hotels which are part
of the Skyline. The other hotels are not part of the
Skyline because they are dominated in terms of price
and distance to the beach by at least one hotel which
is part of the Skyline. Such a Skyline could be use-
ful, for instance, for a travel agency; it helps users
to get a
big picture
of the interesting options. From
the Skyline of hotels, the user can then choose the
most promising hotels and make further inquiries.
Skyline queries can also involve more than two
dimensions and they could depend on the current
position of a user. For instance, (mobile) users could
be interested in restaurants that are near, cheap, and
have good food (according to some rating system).
The distance is based on the current location of the
user. Again, the idea is to give the user the
big
picture
of interesting options and then let the user
make a decision. If the user moves on, the Skyline
should be re-computed continuously in order to give
the user a choice of interesting restaurants based on
the user's new location.
275

Get Proceedings 2002 VLDB Conference now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.