Please use this identifier to cite or link to this item: https://doi.org/10.1145/1559845.1559899
Title: Kernel-Based skyline cardinality estimation
Authors: Zhang, Z. 
Yang, Y.
Cai, R.
Papadias, D.
Tung, A. 
Keywords: Cardinality estimation
Kernel
Non-parametric methods
Skyline
Issue Date: 2009
Source: Zhang, Z.,Yang, Y.,Cai, R.,Papadias, D.,Tung, A. (2009). Kernel-Based skyline cardinality estimation. SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems : 509-521. ScholarBank@NUS Repository. https://doi.org/10.1145/1559845.1559899
Abstract: The skyline of a d-dimensional dataset consists of all points not dominated by others. The incorporation of the skyline operator into practical database systems necessitates an efficient and effective cardinality estimation module. However, existing theoretical work on this problem is limited to the case where all d dimensions are independent of each other, which rarely holds for real datasets. The state of the art Log Sampling (LS) technique simply applies theoretical results for independent dimensions to non-independent data anyway, sometimes leading to large estimation errors. To solve this problem, we propose a novel Kernel-Based (KB) approach that approximates the skyline cardinality with nonparametric methods. Extensive experiments with various real datasets demonstrate that KB achieves high accuracy, even in cases where LS fails. At the same time, despite its numerical nature, the efficiency of KB is comparable to that of LS. Furthermore, we extend both LS and KB to the k-dominant skyline, which is commonly used instead of the conventional skyline for high-dimensional data. © 2009 ACM.
Source Title: SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems
URI: http://scholarbank.nus.edu.sg/handle/10635/41680
ISBN: 9781605585543
DOI: 10.1145/1559845.1559899
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

28
checked on Dec 13, 2017

Page view(s)

65
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


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