Please use this identifier to cite or link to this item: https://doi.org/10.1007/11687238_30
Title: On high dimensional skylines
Authors: Chan, C.-Y. 
Jagadish, H.V.
Tan, K.-L. 
Tung, A.K.H. 
Zhang, Z. 
Issue Date: 2006
Source: Chan, C.-Y.,Jagadish, H.V.,Tan, K.-L.,Tung, A.K.H.,Zhang, Z. (2006). On high dimensional skylines. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3896 LNCS : 478-495. ScholarBank@NUS Repository. https://doi.org/10.1007/11687238_30
Abstract: In many decision-making applications, the skyline query is frequently used to find a set of dominating data points (called skyline points) in a multi-dimensional dataset. In a high-dimensional space skyline points no longer offer any interesting insights as there are too many of them. In this paper, we introduce a novel metric, called skyline frequency that compares and ranks the interestingness of data points based on how often they are returned in the skyline when different number of dimensions (i.e., subspaces) are considered. Intuitively, a point with a high skyline frequency is more interesting as it can be dominated on fewer combinations of the dimensions. Thus, the problem becomes one of finding top-k frequent skyline points. But the algorithms thus far proposed for skyline computation typically do not scale well with dimensionality. Moreover, frequent skyline computation requires that skylines be computed for each of an exponential number of subsets of the dimensions. We present efficient approximate algorithms to address these twin difficulties. Our extensive performance study shows that our approximate algorithm can run fast and compute the correct result on large data sets in high-dimensional spaces. © Springer-Verlag Berlin Heidelberg 2006.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/41699
ISBN: 3540329609
ISSN: 03029743
DOI: 10.1007/11687238_30
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

72
checked on Jan 17, 2018

Page view(s)

40
checked on Jan 22, 2018

Google ScholarTM

Check

Altmetric


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