{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:21:46Z","timestamp":1771024906889,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":56,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642237829","type":"print"},{"value":"9783642237836","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23783-6_42","type":"book-chapter","created":{"date-parts":[[2011,8,17]],"date-time":"2011-08-17T18:41:51Z","timestamp":1313606511000},"page":"661-676","source":"Crossref","is-referenced-by-count":9,"title":["The VC-Dimension of SQL Queries and Selectivity Estimation through Sampling"],"prefix":"10.1007","author":[{"given":"Matteo","family":"Riondato","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mert","family":"Akdere","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U\u01e7ur","family":"\u00c7etintemel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stanley B.","family":"Zdonik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eli","family":"Upfal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Acharya, S., Gibbons, P.B., Poosala, V., Ramaswamy, S.: Join Synopses for Approximate Query Answering. In: SIGMOD 1999 (1999)","DOI":"10.1145\/304182.304207"},{"key":"42_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. John Wiley & Sons, Chichester (2008)","edition":"3"},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Babcock, B., Chaudhuri, S., Das, G.: Dynamic Sample Selection for Approximate Query Processing. In: SIGMOD 2003 (2003)","DOI":"10.1145\/872757.872822"},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Brown, P.G., Haas, P.J.: Techniques for Warehousing of Sample Data. In: ICDE 2006 (2006)","DOI":"10.1109\/ICDE.2006.157"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"Bruno, N., Chaudhuri, S.: Conditional Selectivity for Statistics on Query Expressions. In: SIGMOD 2004 (2004)","DOI":"10.1145\/1007568.1007604"},{"key":"42_CR6","doi-asserted-by":"crossref","unstructured":"Bruno, N., Chaudhuri, S., Gravano, L.: STHoles: a Multidimensional Workload-Aware Histogram. In: SIGMOD 2001 (2001)","DOI":"10.1145\/375663.375686"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Das, G., Narasayya, V.: Optimized Stratified Sampling for Approximate Query Processing. ACM Trans. Database Syst.\u00a032(2), Art. 9 (2007)","DOI":"10.1145\/1242524.1242526"},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Motwani, R., Narasayya, V.: Random Sampling for Histogram Construction: How Much is Enough. In: SIGMOD 1998 (1998)","DOI":"10.1145\/276304.276343"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Motwani, R., Narasayya, V.: On Random Sampling over Joins. In: SIGMOD 1999 (1999)","DOI":"10.1145\/304182.304206"},{"key":"42_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge (2000)"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Chen, M.C., McNamee, L., Matloff, N.S.: Selectivity Estimation Using Homogeneity Measurement. In: ICDE 1990 (1990)","DOI":"10.1109\/ICDE.1990.113482"},{"key":"42_CR12","doi-asserted-by":"crossref","unstructured":"Das, G.: Sampling Methods in Approximate Query Answering Systems. In: Wang, J. (ed.) Encyclopedia of Data Warehousing and Mining. Information Science Publishing (2005)","DOI":"10.4018\/978-1-59140-557-3.ch186"},{"key":"42_CR13","doi-asserted-by":"crossref","unstructured":"Dobra, A.: Histograms Revisited: When are Histograms the Best Approximation Method for Aggregates over Joins? In: PODS 2005 (2005)","DOI":"10.1145\/1065167.1065196"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Estan, C., Naughton, J.F.: End-Biased Samples for Join Cardinality Estimation. In: ICDE 2006 (2006)","DOI":"10.1109\/ICDE.2006.61"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Ganguly, S., Gibbons, P.B., Matias, Y., Silberschatz, A.: Bifocal Sampling for Skew-Resistant Join Size Estimation. In: SIGMOD 1996 (1996)","DOI":"10.1145\/233269.233340"},{"key":"42_CR16","unstructured":"Ganti, V., Lee, M.-L., Ramakrishnan, R.: ICICLES: Self-Tuning Samples for Approximate Query Answering. In: VLDB 2000 (2000)"},{"key":"42_CR17","volume-title":"Database Systems: The Complete Book","author":"H. Garcia-Molina","year":"2002","unstructured":"Garcia-Molina, H., Ullman, J.D., Widom, J.: Database Systems: The Complete Book. Prentice-Hall, Englewood Cliffs (2002)"},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Gemulla, R., Lehner, W., Haas, P.J.: A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets. In: VLDB 2006 (2006)","DOI":"10.1007\/s00778-007-0065-y"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Getoor, L., Taskar, B., Koller, D.: Selectivity Estimation using Probabilistic Models. In: SIGMOD 2001 (2001)","DOI":"10.1145\/375663.375727"},{"key":"42_CR20","doi-asserted-by":"crossref","unstructured":"Gibbons, P.B., Matias, Y.: New Sampling-Based Summary Statistics for Improving Approximate Query Answers. In: SIGMOD 1998 (1998)","DOI":"10.1145\/276304.276334"},{"key":"42_CR21","doi-asserted-by":"crossref","unstructured":"Gryz, J., Liang, D.: Query Selectivity Estimation via Data Mining. In: IIS 2004 (2004)","DOI":"10.1007\/978-3-540-39985-8_4"},{"key":"42_CR22","doi-asserted-by":"crossref","unstructured":"Haas, P.J., Naughton, J.F., Seshadri, S., Swami, A.N.: Fixed-Precision Estimation of Join Selectivity. In: PODS 1993 (1993)","DOI":"10.1145\/153850.153875"},{"key":"42_CR23","doi-asserted-by":"crossref","unstructured":"Haas, P.J., Naughton, J.F., Swami, A.N.: On the Relative Cost of Sampling for Join Selectivity Estimation. In: PODS 1994 (1994)","DOI":"10.1145\/182591.182594"},{"key":"42_CR24","doi-asserted-by":"crossref","unstructured":"Haas, P.J., Swami, A.N.: Sequential Sampling Procedures for Query Size Estimation. In: SIGMOD 1992 (1992)","DOI":"10.1145\/130283.130335"},{"key":"42_CR25","doi-asserted-by":"crossref","unstructured":"Haas, P.J., Swami, A.N.: Sampling-Based Selectivity Estimation for Joins Using Augmented Frequent Value Statistics. In: ICDE 1995 (1995)","DOI":"10.1109\/ICDE.1995.380361"},{"key":"42_CR26","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1006\/jcss.1996.0041","volume":"52","author":"P.J. Haas","year":"1996","unstructured":"Haas, P.J., Naughton, J.F., Seshadri, S., Swami, A.N.: Selectivity and Cost Estimation for Joins Based on Random Sampling. Jour. of Comp. and Sys. Sci.\u00a052, 550\u2013569 (1996)","journal-title":"Jour. of Comp. and Sys. Sci."},{"key":"42_CR27","unstructured":"Haas, P.J.: Hoeffding Inequalities for Join-Selectivity Estimation and Online Aggregation. IBM Research Report RJ 10040 (2000)"},{"key":"42_CR28","doi-asserted-by":"crossref","unstructured":"Harangsri, B., Shepherd, J., Ngu, A.H.H.: Query Size Estimation using Machine Learning. In: DASFAA 1997 (1997)","DOI":"10.1142\/9789812819536_0011"},{"issue":"3","key":"42_CR29","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/s00454-010-9248-1","volume":"45","author":"S. Har-Peled","year":"2011","unstructured":"Har-Peled, S., Sharir, M.: Relative (p,\u03b5)-Approximations in Geometry. Discrete & Computational Geometry\u00a045(3), 462\u2013496 (2011)","journal-title":"Discrete & Computational Geometry"},{"key":"42_CR30","doi-asserted-by":"crossref","unstructured":"Hou, W.-C., Ozsoyoglu, G., Dogdu, E.: Error-Constraint Count Query Evaluation in Relational Databases. In: SIGMOD 1991 (1991)","DOI":"10.1145\/115790.115837"},{"key":"42_CR31","doi-asserted-by":"crossref","unstructured":"Hou, W.-C., Ozsoyoglu, G., Taneja, B.K.: Statistical Estimators for Relational Algebra Expressions. In: PODS 1988 (1988)","DOI":"10.1145\/308386.308455"},{"key":"42_CR32","doi-asserted-by":"crossref","unstructured":"Ioannidis, Y.E., Poosala, V.: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. In: SIGMOD 1995 (1995)","DOI":"10.1145\/223784.223841"},{"key":"42_CR33","unstructured":"Jagadish, H.V., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K.C., Suel, T.: Optimal Histograms with Quality Guarantees. In: VLDB 1998 (1998)"},{"key":"42_CR34","unstructured":"Jin, R., Glimcher, L., Jermaine, C., Agrawal, G.: New Sampling-Based Estimators for OLAP Queries. In: ICDE 2006 (2006)"},{"key":"42_CR35","doi-asserted-by":"crossref","unstructured":"Joshi, S., Jermaine, C.: Robust Stratified Sampling Plans for Low Selectivity Queries. In: ICDE 2008 (2008)","DOI":"10.1109\/ICDE.2008.4497428"},{"issue":"4","key":"42_CR36","doi-asserted-by":"publisher","first-page":"1102","DOI":"10.1145\/1114244.1114251","volume":"30","author":"R. Kaushik","year":"2005","unstructured":"Kaushik, R., Naughton, J.F., Ramakrishnan, R., Chakravarthy, V.T.: Synopses for Query Optimization: a Space-Complexity Perspective. ACM Trans. Database Syst.\u00a030(4), 1102\u20131127 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"42_CR37","doi-asserted-by":"crossref","unstructured":"Larson, P.-A., Lehner, W., Zhou, J., Zabback, P.: Cardinality Estimation Using Sample Views with Quality Assurance. In: SIGMOD 2007 (2007)","DOI":"10.1145\/1247480.1247502"},{"key":"42_CR38","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1006\/jcss.2000.1741","volume":"62","author":"Y. Li","year":"2001","unstructured":"Li, Y., Long, P.M., Srinivasan, A.: Improved Bounds on the Sample Complexity of Learning. Jour. of Comp. and Sys. Sci.\u00a062, 516\u2013527 (2001)","journal-title":"Jour. of Comp. and Sys. Sci."},{"issue":"1","key":"42_CR39","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1006\/jcss.1995.1050","volume":"51","author":"R.J. Lipton","year":"1995","unstructured":"Lipton, R.J., Naughton, J.F.: Query Size Estimation by Adaptive Sampling. J. Comput. Syst. Sci.\u00a051(1), 18\u201325 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"42_CR40","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Naughton, J.F., Schneider, D.A.: Practical Selectivity Estimation through Adaptive Sampling. In: SIGMOD 1990 (1990)","DOI":"10.1145\/93597.93611"},{"key":"42_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-04128-0_29","volume-title":"Algorithms - ESA 2009","author":"M. L\u00f6ffler","year":"2009","unstructured":"L\u00f6ffler, M., Phillips, J.M.: Shape fitting on point sets with probability distributions. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 313\u2013324. Springer, Heidelberg (2009)"},{"issue":"1","key":"42_CR42","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s00778-006-0030-1","volume":"16","author":"V. Markl","year":"2007","unstructured":"Markl, V., Haas, M., Peter, J., Kutsch, Megiddo, N., Srivastava, U., Tran, T.M.: Consistent Selectivity Estimation via Maximum Entropy. The VLDB Journal\u00a016(1), 55\u201376 (2007)","journal-title":"The VLDB Journal"},{"key":"42_CR43","doi-asserted-by":"crossref","unstructured":"Matias, Y., Vitter, J.S., Wang, M.: Wavelet-Based Histograms for Selectivity Estimation. In: SIGMOD 1998 (1998)","DOI":"10.1145\/276304.276344"},{"key":"42_CR44","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, Heidelberg (2002)"},{"key":"42_CR45","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8122-8","volume-title":"Simultaneous Statistical Inference","author":"R.J. Miller","year":"1981","unstructured":"Miller, R.J.: Simultaneous Statistical Inference, 2nd edn. Springer, Heidelberg (1981)","edition":"2"},{"key":"42_CR46","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1023\/B:DAPD.0000018573.35050.25","volume":"15","author":"A.H. Ngu","year":"2004","unstructured":"Ngu, A.H., Harangsri, B., Shepherd, J.: Query Size Estimation for Joins Using Systematic Sampling. Distributed and Parallel Databases\u00a015, 237\u2013275 (2004)","journal-title":"Distributed and Parallel Databases"},{"key":"42_CR47","unstructured":"Olken, F.: Random Sampling from Databases. Ph.D. dissertation, LBL Tech. Report LBL-32883 (1993)"},{"key":"42_CR48","doi-asserted-by":"crossref","unstructured":"Poosala, V., Haas, P.J., Ioannidis, Y.E., Shekita, E.J.: Improved Histograms for Selectivity Estimation of Range Predicates. In: SIGMOD 1996 (1996)","DOI":"10.1145\/233269.233342"},{"key":"42_CR49","unstructured":"Poosala, V., Ioannidis, Y.E.: Selectivity Estimation without the Attribute Value Independence Assumption. In: VLDB 1997 (1997)"},{"key":"42_CR50","doi-asserted-by":"crossref","unstructured":"R\u00e9, C., Suciu, D.: Understanding Cardinality Estimation Using Entropy Maximization. In: PODS 2010 (2010)","DOI":"10.1145\/1807085.1807095"},{"key":"42_CR51","doi-asserted-by":"crossref","unstructured":"Riondato, M., Akdere, M., \u00c7etintemel, U., Zdonik, S.B., Upfal, E.: The VC-Dimension of SQL Queries and Selectivity Estimation Through Sampling. CoRR abs\/1101.5805 (2011)","DOI":"10.1007\/978-3-642-23783-6_42"},{"key":"42_CR52","doi-asserted-by":"crossref","unstructured":"Srivastava, U., Haas, P.J., Markl, V., Kutsch, M., Tran, T.: ISOMER: Consistent Histogram Construction Using Query Feedback. In: ICDE 2006 (2006)","DOI":"10.1109\/ICDE.2006.84"},{"issue":"2","key":"42_CR53","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the Uniform Convergence of Relative Frequencies of Events to their Probabilities. Theory of Probability and its Applications\u00a016(2), 264\u2013280 (1971)","journal-title":"Theory of Probability and its Applications"},{"key":"42_CR54","unstructured":"Wang, H., Sevcik, K.C.: A Multi-Dimensional Histogram for Selectivity Estimation and Fast Approximate Query Answering. In: CASCON 2003 (2003)"},{"key":"42_CR55","unstructured":"Wang, M., Vitter, J.S., Iyer, B.R.: Selectivity Estimation in the Presence of Alphanumeric Correlations.In: ICDE 1997 (1997)"},{"key":"42_CR56","doi-asserted-by":"crossref","unstructured":"Wu, Y.-L., Agrawal, D., El Abbadi, A.: Applying the Golden Rule of Sampling for Query Estimation. In: SIGMOD 2001 (2001)","DOI":"10.1145\/375663.375724"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23783-6_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:18:20Z","timestamp":1638317900000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23783-6_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237829","9783642237836"],"references-count":56,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23783-6_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}