|
|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/174
|
| Title: | An optimal and progressive algorithm for skyline queries |
| Authors: | Papadias, Dimitris
Tao, Yufei
Fu, Greg
Seeger, Bernhard |
| Keywords: | Skyline
NN
Nearest neighbors
BBS
Branch-and-bound skyline |
| Issue Date: | 2003 |
| Citation: | To be published in Proceedings / ACM-SIGMOD International Conference on Management of Data, San Diego, CA, USA, 9-12 June 2003 |
| Abstract: | 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 |
| URI: | http://hdl.handle.net/1783.1/174 |
| Appears in Collections: | CSE Conference Papers
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| SIGMOD03Skyline.pdf | | 202Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
