Selecting Stars: The k Most Representative Skyline Operator
- 1 April 2007
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2007 IEEE 23rd International Conference on Data Engineering
Abstract
Skyline computation has many applications including multi-criteria decision making. In this paper, we study the problem of selecting k skyline points so that the number of points, which are dominated by at least one of these k skyline points, is maximized. We first present an efficient dynamic programming based exact algorithm in a 2d-space. Then, we show that the problem is NP-hard when the dimensionality is 3 or more and it can be approximately solved by a polynomial time algorithm with the guaranteed approximation ratio 1-1/e. To speed-up the computation, an efficient, scalable, index-based randomized algorithm is developed by applying the FM probabilistic counting technique. A comprehensive performance evaluation demonstrates that our randomized technique is very efficient, highly accurate, and scalable.Keywords
This publication has 21 references indexed in Scilit:
- DADAPublished by Association for Computing Machinery (ACM) ,2006
- Refreshing the skyPublished by Association for Computing Machinery (ACM) ,2006
- Maintaining sliding window skylines on data streamsIEEE Transactions on Knowledge and Data Engineering, 2006
- Approximately Dominating RepresentativesLecture Notes in Computer Science, 2004
- Dynamic Maintenance of Maxima of 2-d Point SetsSIAM Journal on Computing, 2000
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- Probabilistic counting algorithms for data base applicationsJournal of Computer and System Sciences, 1985
- R-treesPublished by Association for Computing Machinery (ACM) ,1984
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975