HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5998
Title: Kernel-based skyline cardinality estimation
Authors: Zhang, Zhenjie
Yang, Yin
Cai, Ruichu
Papadias, Dimitris
Tung, Anthony K. H.
Keywords: Skyline
Cardinality estimation
Kernel
Non-parametric methods
Issue Date: 2009
Citation: To appear in the Proceedings of the ACM Conference on the Management of Data (SIGMOD), Providence, Rhode Island, U.S.A., June 29-July 2, 2009
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.
Rights: © ACM, 2009. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version will be published in Proceedings of the ACM Conference on the Management of Data (SIGMOD), Providence, Rhode Island, U.S.A., June 29-July 2, 2009.
URI: http://hdl.handle.net/1783.1/5998
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
SIGMOD09-SCE.pdf684KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.