Selecting Stars: The k Most Representative Skyline Operator

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 progr...

Full description

Saved in:
Bibliographic Details
Main Authors: Xuemin Lin, Yidong Yuan, Qing Zhang, Ying Zhang
Format: Conference Proceeding
Language:English
Subjects:
Application software
Approximation algorithms
Australia
Computer applications
Computer science
Costs
Decision making
Dynamic programming
Polynomials
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1063-6382
2375-026X
DOI:10.1109/ICDE.2007.367854