Progressive skyline computation in database systems
Top Cited Papers
- 1 March 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 30 (1), 41-82
- https://doi.org/10.1145/1061318.1061320
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 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.Keywords
This publication has 19 references indexed in Scilit:
- Determining the Convex Hull in Large Multidimensional DatabasesLecture Notes in Computer Science, 2001
- Efficient cost models for spatial queries using R-treesIEEE Transactions on Knowledge and Data Engineering, 2000
- Interactive data analysis: the Control projectComputer, 1999
- Comparison of access methods for time-evolving dataACM Computing Surveys, 1999
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- Computing dominances in EnInformation Processing Letters, 1991
- On the average number of maxima in a set of vectorsInformation Processing Letters, 1989
- Computational GeometryPublished by Springer Science and Business Media LLC ,1985
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975
- Drawing Contours from Arbitrary Data PointsThe Computer Journal, 1974