Please use this identifier to cite or link to this item:
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
Query processing
Issue Date: 2006
Citation: 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.
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
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.

Google ScholarTM



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