{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T02:57:48Z","timestamp":1772333868348,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>\n            We study the problem of efficiently estimating counts for queries involving complex filters, such as user-defined functions, or predicates involving self-joins and correlated subqueries. For such queries, traditional sampling techniques may not be applicable due to the complexity of the filter preventing sampling over joins, and sampling after the join may not be feasible due to the cost of computing the full join. The other natural approach of training and using an inexpensive classifier to estimate the count instead of the expensive predicate suffers from the difficulties in training a good classifier and giving meaningful confidence intervals. In this paper we propose a new method of\n            <jats:italic>learning to sample<\/jats:italic>\n            where we combine the best of both worlds by using sampling in two phases. First, we use samples to learn a probabilistic classifier, and then use the classifier to design a stratified sampling method to obtain the final estimates. We theoretically analyze algorithms for obtaining an optimal stratification, and compare our approach with a suite of natural alternatives like quantification learning, weighted and stratified sampling, and other techniques from the literature. We also provide extensive experiments in diverse use cases using multiple real and synthetic datasets to evaluate the quality, efficiency, and robustness of our approach.\n          <\/jats:p>","DOI":"10.14778\/3368289.3368302","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:17:35Z","timestamp":1599794255000},"page":"390-402","source":"Crossref","is-referenced-by-count":16,"title":["Learning to sample"],"prefix":"10.14778","volume":"13","author":[{"given":"Brett","family":"Walenz","sequence":"first","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872822"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914867"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","DOI":"10.1561\/9781601985170","volume-title":"Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends\u00ae in Databases, 4(1--3):1--294","author":"Cormode G.","year":"2011"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3117807"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130335"},{"key":"e_1_2_1_9_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-030-18579-4_1","volume-title":"DASFAA (2)","author":"Halford M.","year":"2019"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723715"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497428"},{"issue":"1","key":"e_1_2_1_13_1","first-page":"181","article-title":"Sampling-based estimators for subset-based queries","volume":"18","author":"Joshi S.","year":"2009","journal-title":"PVLDB"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","DOI":"10.4135\/9781412984683","volume-title":"Introduction to survey sampling","author":"Kalton G.","year":"1983"},{"key":"e_1_2_1_15_1","volume-title":"CIDR 2019, 9th Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 13--16, 2019, Online Proceedings","author":"Kipf A.","year":"2019"},{"key":"e_1_2_1_16_1","volume-title":"CIDR 2019, 9th Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 13--16, 2019, Online Proceedings","author":"Kraska T.","year":"2019"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183751"},{"key":"e_1_2_1_19_1","first-page":"25","article-title":"Stratified random sampling over streaming and stored data. In Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon","volume":"2019","author":"Nguyen T. D.","year":"2019","journal-title":"Portugal, March 26--29"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645913.671474"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196905"},{"key":"e_1_2_1_23_1","volume-title":"Lshtc: A benchmark for large-scale text classification","author":"Partalas I.","year":"2015"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04898-2_501"},{"key":"e_1_2_1_25_1","unstructured":"B. Walenz S. Sintos S. Roy and J. Yang. Learning to sample: Counting with complex queries. https:\/\/arxiv.org\/abs\/1906.09335.  B. Walenz S. Sintos S. Roy and J. Yang. Learning to sample: Counting with complex queries. https:\/\/arxiv.org\/abs\/1906.09335."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610505"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3368289.3368302","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:42:39Z","timestamp":1672220559000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3368289.3368302"}},"subtitle":["counting with complex queries"],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.14778\/3368289.3368302"],"URL":"https:\/\/doi.org\/10.14778\/3368289.3368302","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}