{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:30:13Z","timestamp":1761294613482,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel Science Foundations","award":["1595\/19"],"award-info":[{"award-number":["1595\/19"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3589935","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"361-371","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sampling Big Ideas in Query Optimization"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3926-8237","authenticated-orcid":false,"given":"Edith","family":"Cohen","sequence":"first","affiliation":[{"name":"Google Research & Tel Aviv University, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"P. K. Agarwal S. Har-Peled and K. R. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and computational geometry MSRI. University Press."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.82"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.93"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365694"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"volume-title":"All-Distances Sketches","author":"Cohen E.","key":"e_1_3_2_1_8_1","unstructured":"E. Cohen. 2014a. All-Distances Sketches, Revisited: HIP estimators for massive graphs analysis. In PODS. ACM. http:\/\/arxiv.org\/abs\/1306.3284"},{"key":"e_1_3_2_1_9_1","unstructured":"E. Cohen. 2014b. Distance Queries from Sampled Data: Accurate and Efficient. In KDD. ACM. full version: http:\/\/arxiv.org\/abs\/1203.4903."},{"key":"e_1_3_2_1_11_1","volume-title":"All-Distances Sketches","author":"Cohen E.","year":"2015","unstructured":"E. Cohen. 2015a. All-Distances Sketches, Revisited: HIP estimators for massive graphs analysis. TKDE (2015). http:\/\/arxiv.org\/abs\/1306.3284"},{"volume-title":"HotWeb","author":"Cohen E.","key":"e_1_3_2_1_12_1","unstructured":"E. Cohen. 2015b. Multi-Objective Weighted Sampling. In HotWeb. IEEE. full version: http:\/\/arxiv.org\/abs\/1509.07445."},{"key":"e_1_3_2_1_14_1","unstructured":"E. Cohen. 2017. HyperLogLog Hyper Extended: Sketches for Concave Sublinear Frequency Statistics. In KDD. ACM. full version: https:\/\/arxiv.org\/abs\/1607.06517."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3234338"},{"key":"e_1_3_2_1_16_1","volume-title":"Quality Guarantees: Adaptivity with One2all pps. In AAAI","author":"Cohen E.","year":"2018","unstructured":"E. Cohen, S. Chechik, and H. Kaplan. 2018. Clustering Small Samples with Quality Guarantees: Adaptivity with One2all pps. In AAAI. http:\/\/arxiv.org\/abs\/1706.03607"},{"volume-title":"Proc. ACM SIGMETRICS\/Performance.","author":"Cohen E.","key":"e_1_3_2_1_17_1","unstructured":"E. Cohen, G. Cormode, and N. Duffield. 2012. Don't Let The Negatives Bring You Down: Sampling from Streams of Signed Updates. In Proc. ACM SIGMETRICS\/Performance."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2963103"},{"key":"e_1_3_2_1_19_1","volume-title":"Social Networks: Closeness, Node Labels, and Random Edge Lengths. In COSN. ACM.","author":"Cohen E.","year":"2013","unstructured":"E. Cohen, D. Delling, F. Fuchs, A. Goldberg, M. Goldszmidt, and R. Werneck. 2013. Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths. In COSN. ACM."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"E. Cohen D. Delling T. Pajor and R. F. Werneck. 2014a. Computing Classic Closeness Centrality at Scale. In COSN. ACM. http:\/\/arxiv.org\/abs\/1409.0035","DOI":"10.1145\/2660460.2660465"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/10079817X"},{"key":"e_1_3_2_1_22_1","volume-title":"Comput. System Sci.","volume":"80","author":"Cohen E.","year":"2014","unstructured":"E. Cohen, N. Duffield, H. Kaplan, C. Lund, and M. Thorup. 2014b. Algorithms and estimators for accurate summarization of Unaggregated Data Streams. J. Comput. System Sci. , Vol. 80 (2014)."},{"key":"e_1_3_2_1_23_1","unstructured":"E. Cohen and O. Geri. 2019. Sampling Sketches for Concave Sublinear Functions of Frequencies. In NeurIPS. http:\/\/papers.nips.cc\/paper\/8417-sampling-sketches-for-concave-sublinear-functions-of-frequencies"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"E. Cohen and H. Kaplan. 2004. Spatially-decaying aggregation over a network: model and algorithms. In SIGMOD. ACM.","DOI":"10.1145\/1007568.1007647"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.016"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"E. Cohen and H. Kaplan. 2007 b. Summarizing data using Bottom-k sketches. In ACM PODC.","DOI":"10.1145\/1281100.1281133"},{"volume-title":"Proceedings of the 34th VLDB Conference. http:\/\/arxiv.org\/abs\/0802","author":"Cohen E.","key":"e_1_3_2_1_27_1","unstructured":"E. Cohen and H. Kaplan. 2008. Tighter estimation using bottom-k sketches. In Proceedings of the 34th VLDB Conference. http:\/\/arxiv.org\/abs\/0802.3448"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"E. Cohen and H. Kaplan. 2009. Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates. In ACM SIGMETRICS.","DOI":"10.1145\/1555349.1555379"},{"key":"e_1_3_2_1_29_1","volume-title":"Proc. of the 2011 ACM Symp. on Principles of Database Systems (PODS","author":"Cohen E.","year":"2011","unstructured":"E. Cohen and H. Kaplan. 2011. Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information. In Proc. of the 2011 ACM Symp. on Principles of Database Systems (PODS 2011). ACM. full version: https:\/\/arxiv.org\/abs\/1109.1325."},{"volume-title":"International Workshop on Randomization and Computation (RANDOM). full version: http:\/\/arxiv.org\/abs\/1206","author":"Cohen E.","key":"e_1_3_2_1_30_1","unstructured":"E. Cohen and H. Kaplan. 2013. What you can do with Coordinated Samples. In The 17th. International Workshop on Randomization and Computation (RANDOM). full version: http:\/\/arxiv.org\/abs\/1206.5637."},{"key":"e_1_3_2_1_31_1","volume-title":"Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments. VLDB","volume":"2","author":"Cohen E.","year":"2009","unstructured":"E. Cohen, H. Kaplan, and S. Sen. 2009. Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments. VLDB , Vol. 2 (2009). full version: http:\/\/arxiv.org\/abs\/0906.4560."},{"key":"e_1_3_2_1_32_1","unstructured":"E. Cohen R. Pagh and D. P. Woodruff. 2020. WOR and p's: Sketches for $ell_p$-Sampling Without Replacement. In NeurIPS. https:\/\/arxiv.org\/abs\/2007.06744"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1139720.1712365"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314696"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1138831.1711169"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"C. Estan and G. Varghese. 2002. New directions in traffic measurement and accounting. In SIGCOMM. ACM.","DOI":"10.1145\/633025.633056"},{"key":"e_1_3_2_1_37_1","volume-title":"Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Analysis of Algorithms (AofA). DMTCS.","author":"Flajolet P.","year":"2007","unstructured":"P. Flajolet, E. Fusy, O. Gandouet, and F. Meunier. 2007. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Analysis of Algorithms (AofA). DMTCS."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"P. Gibbons and Y. Matias. 1998. New sampling-based summary statistics for improving approximate query answers. In SIGMOD. ACM.","DOI":"10.1145\/276305.276334"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"S. Har-Peled and S. Mazumdar. 2004. On Coresets for K-means and K-median Clustering. In STOC. ACM.","DOI":"10.1145\/1007352.1007400"},{"volume-title":"Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement. 222--233","author":"Hohn N.","key":"e_1_3_2_1_41_1","unstructured":"N. Hohn and D. Veitch. 2003. Inverting sampled traffic. In Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement. 222--233."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483446"},{"key":"e_1_3_2_1_43_1","volume-title":"Proc. 41st IEEE Annual Symposium on Foundations of Computer Science. IEEE, 189--197","author":"Indyk P.","year":"2001","unstructured":"P. Indyk. 2001. Stable distributions, pseudorandom generators, embeddings and data stream computation. In Proc. 41st IEEE Annual Symposium on Foundations of Computer Science. IEEE, 189--197."},{"volume-title":"Proc. 30th Annual ACM Symposium on Theory of Computing. ACM, 604--613","author":"Indyk P.","key":"e_1_3_2_1_44_1","unstructured":"P. Indyk and R. Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Proc. 30th Annual ACM Symposium on Theory of Computing. ACM, 604--613."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1971.10482286"},{"key":"e_1_3_2_1_46_1","volume-title":"Vol 2, Seminumerical Algorithms","author":"Knuth D. E.","unstructured":"D. E. Knuth. 1968. The Art of Computer Programming, Vol 2, Seminumerical Algorithms 1st ed.). Addison-Wesley.","edition":"1"},{"key":"e_1_3_2_1_47_1","volume-title":"Vol 2, Seminumerical Algorithms","author":"Knuth D. E.","unstructured":"D. E. Knuth. 1998. The Art of Computer Programming, Vol 2, Seminumerical Algorithms 2nd ed.). Addison-Wesley.","edition":"2"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"J. Misra and D. Gries. 1982. Finding Repeated Elements. Technical Report. Cornell University.","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--73420--8_7"},{"key":"e_1_3_2_1_51_1","first-page":"149","article-title":"Sequential Poisson sampling","volume":"14","author":"Ohlsson E.","year":"1998","unstructured":"E. Ohlsson. 1998. Sequential Poisson sampling. J. Official Statistics , Vol. 14, 2 (1998), 149--162.","journal-title":"J. Official Statistics"},{"key":"e_1_3_2_1_52_1","volume-title":"Coordination of PPS Samples Over Time. In The 2nd International Conference on Establishment Surveys. American Statistical Association, 255--264","author":"Ohlsson E.","year":"2000","unstructured":"E. Ohlsson. 2000. Coordination of PPS Samples Over Time. In The 2nd International Conference on Establishment Surveys. American Statistical Association, 255--264."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.104"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692620"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(96)00185-1"},{"key":"e_1_3_2_1_56_1","volume-title":"Proc. of the Section on Survey Research Methods. American Statistical Association","author":"Saavedra P. J.","year":"1995","unstructured":"P. J. Saavedra. 1995. Fixed sample size PPS approximations with a permanent random number. In Proc. of the Section on Survey Research Methods. American Statistical Association, Alexandria, VA, 697--700."},{"volume-title":"Proceedings of the 33th Annual ACM Symposium on Theory of Computing","author":"Thorup M.","key":"e_1_3_2_1_57_1","unstructured":"M. Thorup and U. Zwick. 2001. Approximate distance oracles. In Proceedings of the 33th Annual ACM Symposium on Theory of Computing, Crete, Greece. 183--192."},{"volume-title":"Sampling Algorithms","author":"Till\u00e9 Y.","key":"e_1_3_2_1_58_1","unstructured":"Y. Till\u00e9. 2006. Sampling Algorithms. Springer-Verlag, New York."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"D. Ting. 2014. Streamed approximate counting of distinct elements: Beating Optimal Batch Methods. In KDD. ACM.","DOI":"10.1145\/2623330.2623669"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"}],"event":{"name":"SIGMOD\/PODS '23: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Seattle WA USA","acronym":"SIGMOD\/PODS '23"},"container-title":["Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3589935","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3589935","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:29Z","timestamp":1750178789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3589935"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":57,"alternative-id":["10.1145\/3584372.3589935","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3589935","relation":{},"subject":[],"published":{"date-parts":[[2023,6,18]]},"assertion":[{"value":"2023-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}