Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2272

Progressive skyline computation in database systems

Authors Papadias, D
Tao, YF
Fu, G
Seeger, B
Issue Date 2005
Source ACM transactions on database systems , v. 30, (1), 2005, MAR, p. 41-82
Summary 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 article we develop branch-and-bound skyline (BBS), an algorithm based on nearest-neighbor search, which is I/O optimal, that is, 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.
Subjects
ISSN 0362-5915
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.
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST
Files in this item:
File Description Size Format
PapaTODS05skyline.pdf 516071 B Adobe PDF