Please use this identifier to cite or link to this item:

An Optimal and Progressive Algorithm for Skyline Queries

Authors Papadias, Dimitris
Tao, Yufei
Fu, Greg
Seeger, Bernhard
Issue Date 2003
Source Proceedings of the ACM Conference on the Management of Data (SIGMOD), San Diego, CA, June 9-12 , pp. 443-454
Summary The skyline of a set of d-dimensional points contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive (or online) algorithms that can quickly return the first skyline points without having to read the entire data file. Currently, the most efficient algorithm is NN (nearest neighbors), which applies the divide-and-conquer framework on datasets indexed by R-trees. Although NN has some desirable features (such as high speed for returning the initial skyline points, applicability to arbitrary data distributions and dimensions), it also presents several inherent disadvantages (need for duplicate elimination if d>2, multiple accesses of the same node, large space overhead). In this paper we develop BBS (branch-and-bound skyline), a progressive algorithm also based on nearest neighbor search, which is IO optimal, i.e., it performs a single access only to those R-tree nodes that may contain skyline points. Furthermore, it does not retrieve duplicates and its space overhead is significantly smaller than that of NN. Finally, BBS is simple to implement and can be efficiently applied to a variety of alternative skyline queries. An analytical and experimental comparison shows that BBS outperforms NN (usually by orders of magnitude) under all problem instances.
Rights © ACM, 2003. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings / ACM-SIGMOD International Conference on Management of Data, San Diego, CA, USA, 9-12 June 2003
Language English
Format Conference paper
Files in this item:
File Description Size Format
SIGMOD03Skyline.pdf 207359 B Adobe PDF