|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/2272
|
| Title: | Progressive skyline computation in database systems |
| Authors: | Papadias, Dimitris
Tao, Yufei
Fu, Greg
Seeger, Bernhard |
| Keywords: | Skyline query
Branch and bound algorithms
Multi-dimensional access methods |
| Issue Date: | Mar-2005 |
| Citation: | ACM transactions on database systems, v. 30, iss. 1, March 2005, p. 41-82 |
| Abstract: | The skyline of a d-dimensional dataset 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 methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this paper we develop BBS (b̲ranch-and-b̲ound s̲kyline), an algorithm based on nearest neighbor search, which is I/O optimal, i.e., it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing. |
| Rights: | © ACM, 2005. 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 ACM transaction on database systems, vol. 30, iss. 1, March 2005. |
| URI: | http://hdl.handle.net/1783.1/2272 |
| Appears in Collections: | CSE Journal/Magazine Articles
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| PapaTODS05skyline.pdf | pre-published version | 503Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
