HKUST Library Institutional Repository Banner

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 SizeFormat
PapaTODS05skyline.pdfpre-published version503KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.