Please use this identifier to cite or link to this item: https://doi.org/10.1145/1142473.1142530
Title: Finding k-dominant skylines in high dimensional space
Authors: Chan, C.-Y. 
Jagadish, H.V.
Tan, K.-L. 
Tung, A.K.H. 
Zhang, Z. 
Keywords: Data mining
High dimensional space
K-dominant
Query processing
Ranking
Skyline
Issue Date: 2006
Source: Chan, C.-Y.,Jagadish, H.V.,Tan, K.-L.,Tung, A.K.H.,Zhang, Z. (2006). Finding k-dominant skylines in high dimensional space. Proceedings of the ACM SIGMOD International Conference on Management of Data : 503-514. ScholarBank@NUS Repository. https://doi.org/10.1145/1142473.1142530
Abstract: Given a d-dimensional data set, a point p dominates another point q if it is better than or equal to q in all dimensions and better than q in at least one dimension. A point is a skyline point if there does not exists any point that can dominate it. Skyline queries, which return skyline points, are useful in many decision making applications.Unfortunately, as the number of dimensions increases, the chance of one point dominating another point is very low. As such, the number of skyline points become too numerous to offer any interesting insights. To find more important and meaningful skyline points in high dimensional space, we propose a new concept, called k-dominant skyline which relaxes the idea of dominance to k-dominance. A point p is said to k-dominate another point q if there are k d dimensions in which p is better than or equal to q and is better in at least one of these k dimensions. A point that is not k-dominated by any other points is in the k-dominant skyline.We prove various properties of k-dominant skyline. In particular, because k-dominant skyline points are not transitive, existing skyline algorithms cannot be adapted for k-dominant skyline. We then present several new algorithms for finding k-dominant skyline and its variants. Extensive experiments show that our methods can answer different queries on both synthetic and real data sets efficiently. Copyright 2006 ACM.
Source Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
URI: http://scholarbank.nus.edu.sg/handle/10635/41081
ISBN: 1595934340
ISSN: 07308078
DOI: 10.1145/1142473.1142530
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

269
checked on Dec 5, 2017

Page view(s)

45
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.