Kernel-based skyline cardinality estimation

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.

REFERENCES

• 1: Ilaria Bartolini , Paolo Ciaccia , Marco Patella, Efficient sort-based skyline evaluation, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-49, November 2008 [doi>10.1145/1412331.1412343]
• 2: Jon L. Bentley , Kenneth L. Clarkson , David B. Levine, Fast linear expected-time alogorithms for computing maxima and convex hulls, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.179-187, January 22-24, 1990, San Francisco, California, United States
• 3: J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 [doi>10.1145/322092.322095]
• 4: Björn Blohsfeld , Dieter Korus , Bernhard Seeger, A comparison of selectivity estimators for range queries on metric attributes, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.239-250, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: Börzsönyi, S., Kossmann, D., Stocker, K. The Skyline Operator. ICDE, 2001.
• 6: Casella, G., Berger, R., Statistical Inference. Duxbury Press, 2001.
• 7: Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066181]
• 8: Chee-Yong Chan , H. V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , Zhenjie Zhang, Finding k-dominant skylines in high dimensional space, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142530]
• 9: Surajit Chaudhuri , Nilesh Dalvi , Raghav Kaushik, Robust Cardinality and Cost Estimation for Skyline Operator, Proceedings of the 22nd International Conference on Data Engineering, p.64, April 03-07, 2006 [doi>10.1109/ICDE.2006.131]
• 10: Jan Chomicki, Querying with Intrinsic Preferences, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.34-51, March 25-27, 2002
• 11: Chomicki, J., Godfrey, P., Gryz, J., Liang, D. Skyline with Presorting. ICDE, 2003.
• 12: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 13: Fridman, J. Exploratory Projection Pursuit. Journal of American Statistics Association, 82:249--266, 1987.
• 14: Godfrey, P. Skyline Cardinality for Relational Processing. FoIKS, 2004.
• 15: Parke Godfrey , Ryan Shipley , Jarek Gryz, Algorithms and analyses for maximal vector computation, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.1, p.5-28, January 2007 [doi>10.1007/s00778-006-0029-7]
• 16: Dimitrios Gunopulos , George Kollios , J. Tsotras , Carlotta Domeniconi, Selectivity estimators for multidimensional range queries over real attributes, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.137-154, April 2005 [doi>10.1007/s00778-003-0090-4]
• 17: Peter J. Haas , Arun N. Swami, Sequential sampling procedures for query size estimation, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.341-350, June 02-05, 1992, San Diego, California, United States
• 18: Hwang, J.-N., Lay, S.-R., Lippman, A. Nonparametric Multivariate Density Estimation: A Comparative Study. IEEE Trans. on Signal Processing, 42(10): 2795--2810, 1994.
• 19: Hwang, J.-N., Lay, S.-R., Lippman, A. Unsupervised Learning for Multivariate Probability Density Estimation: Radial Basis and Projection Pursuit. IEEE Conf. on Neural Networks, 1994.
• 20: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 21: Koltun, V., Papadimitriou, C. Approximately Dominating Representatives. ICDT, 2005.
• 22: Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
• 23: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 24: Ken C. K. Lee , Baihua Zheng , Huajing Li , Wang-Chien Lee, Approaching the skyline in Z order, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 25: Xuemin Lin , Yidong Yuan , Wei Wang , Hongjun Lu, Stabbing the Sky: Efficient Skyline Computation over Sliding Windows, Proceedings of the 21st International Conference on Data Engineering, p.502-513, April 05-08, 2005 [doi>10.1109/ICDE.2005.137]
• 26: Michael Morse , Jignesh M. Patel , H. V. Jagadish, Efficient skyline computation over low-cardinality domains, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 27: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005 [doi>10.1145/1061318.1061320]
• 28: Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 29: Jian Pei , Wen Jin , Martin Ester , Yufei Tao, Catching the best views of skyline: a semantic approach based on decisive subspaces, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 30: Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
• 31: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, New York, NY, 1992
• 32: Dimitris Sacharidis , Stavros Papadopoulos , Dimitris Papadias, Topologically Sorted Skylines for Partially Ordered Domains, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1072-1083, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.129]
• 33: Mehdi Sharifzadeh , Cyrus Shahabi, The spatial skyline queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 34: Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
• 35: Yufei Tao , Dimitris Papadias, Maintaining Sliding Window Skylines on Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.18 n.3, p.377-391, March 2006 [doi>10.1109/TKDE.2006.48]
• 36: Yufei Tao , Xiaokui Xiao , Jian Pei, SUBSKY: Efficient Computation of Skylines in Subspaces, Proceedings of the 22nd International Conference on Data Engineering, p.65, April 03-07, 2006 [doi>10.1109/ICDE.2006.149]
• 37: Tian Xia , Donghui Zhang, Refreshing the sky: the compressed skycube with efficient support for frequent updates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142529]
• 38: Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , Qing Zhang, Efficient computation of the skyline cube, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
cardinality estimation, kernel, non-parametric methods, skyline