{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T18:37:32Z","timestamp":1767983852906,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1637546, CCF-1815316"],"award-info":[{"award-number":["CCF-1637546, CCF-1815316"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451032","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"556-569","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Information theoretic limits of cardinality estimation: Fisher meets Shannon"],"prefix":"10.1145","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[{"name":"University of Michigan, USA"}]},{"given":"Dingyu","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Statistical theory: a concise introduction","author":"Abramovich Felix","unstructured":"Felix Abramovich and Ya'acov Ritov. 2013. Statistical theory: a concise introduction. CRC Press."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 623\u2013632","author":"Bar-Yossef Ziv","unstructured":"Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 623\u2013632."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562787"},{"key":"e_1_3_2_1_7_1","volume-title":"Mathematical statistics: Basic ideas and selected topics. 2d. ed","author":"Bickel P","year":"2001","unstructured":"P Bickel and K Doksum. 2001. Mathematical statistics: Basic ideas and selected topics. 2d. ed. vol. 1 prentice hall. Upper Saddle River, NJ (2001)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361194"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309193"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SEQUEN.1997.666900"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.31"},{"key":"e_1_3_2_1_12_1","unstructured":"G. Casella and R. L. Berger. 2002. Statistical Inference 2nd Ed. Brooks\/Cole Belmont CA."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3492"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2011.ap10217"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746620"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9469.2010.00727.x"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2411606"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453884"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3097999"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2004.1320018"},{"key":"e_1_3_2_1_22_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory (Second Edition). Wiley."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_55"},{"key":"e_1_3_2_1_25_1","volume-title":"New Cardinality Estimation Methods for HyperLogLog Sketches. CoRR abs\/1706.07290","author":"Ertl Otmar","year":"2017","unstructured":"Otmar Ertl. 2017. New Cardinality Estimation Methods for HyperLogLog Sketches. CoRR abs\/1706.07290 (2017). arxiv:1706.07290 http:\/\/arxiv.org\/abs\/1706.07290"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220089"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2006.882836"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241657"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Philippe Flajolet \\'Eric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm In Proceedings of the 18th International Meeting on Probabilistic Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA). Discrete Mathematics & Theoretical Computer Science 127\u2013146.","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.020"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Ahmed Helmi J\u00e9r\u00e9mie Lumbroso Conrado Mart\\'inez and Alfredo Viola. 2012. Data Streams as Random Permutations: the Distinct Element Problem In Proceedings of the 23rd International Meeting on Probabilistic Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA). Discrete Mathematics & Theoretical Computer Science 323\u2013338.","DOI":"10.46298\/dmtcs.3002"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238202"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483706"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_2_1_38_1","volume-title":"Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm. CoRR abs\/1708.06839","author":"Lang Kevin J.","year":"2017","unstructured":"Kevin J. Lang. 2017. Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm. CoRR abs\/1708.06839 (2017). arxiv:1708.06839"},{"key":"e_1_3_2_1_39_1","volume-title":"Cardinality estimation using Gumbel distribution. CoRR abs\/2008.07590","author":"Lukasiewicz Aleksander","year":"2020","unstructured":"Aleksander \\Lukasiewicz and Przemys\u0142aw Uzna\\'nski. 2020. Cardinality estimation using Gumbel distribution. CoRR abs\/2008.07590 (2020). arxiv:2008.07590 https:\/\/arxiv.org\/abs\/2008.07590"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.2780"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/290159.290162"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380844"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1340771.1340773"},{"key":"e_1_3_2_1_44_1","volume-title":"Information theoretic limits of cardinality estimation: Fisher meets Shannon. arXiv preprint arXiv:2007.08051","author":"Pettie Seth","year":"2020","unstructured":"Seth Pettie and Dingyu Wang. 2020. Information theoretic limits of cardinality estimation: Fisher meets Shannon. arXiv preprint arXiv:2007.08051 (2020)."},{"key":"e_1_3_2_1_45_1","volume-title":"Simple and Efficient Cardinality Estimation in Data Streams. CoRR abs\/2008.08739","author":"Pettie Seth","year":"2020","unstructured":"Seth Pettie, Dingyu Wang, and Longhui Yin. 2020. Simple and Efficient Cardinality Estimation in Data Streams. CoRR abs\/2008.08739 (2020). arxiv:2008.08739 https:\/\/arxiv.org\/abs\/2008.08739"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 4th International Workshop on Foundations of Mobile Computing (DIALM-POMC).","author":"Scheuermann Bj\u00f6rn","year":"2007","unstructured":"Bj\u00f6rn Scheuermann and Martin Mauve. 2007. Near-Optimal Compression of Probabilistic Counting Sketches for Networking Applications. In Proceedings of the 4th International Workshop on Foundations of Mobile Computing (DIALM-POMC)."},{"key":"e_1_3_2_1_47_1","volume-title":"Cardinality Estimation. ([n.\\,d.]). https:\/\/www.cs.princeton.edu\/~rs\/talks\/Cardinality.pdf Presentation delivered at AofA","author":"Sedgewick Robert","year":"2016","unstructured":"Robert Sedgewick. [n.d.]. Cardinality Estimation. ([n.\\,d.]). https:\/\/www.cs.princeton.edu\/~rs\/talks\/Cardinality.pdf Presentation delivered at AofA (2016), Knuth-80 (2018), and Dagstuhl 19051 (2019). https:\/\/www.cs.princeton.edu\/~rs\/talks\/Cardinality.pdf."},{"key":"e_1_3_2_1_48_1","unstructured":"The Apache Foundation. 2019. Apache DataSketches: A software library of stochastic streaming algorithms. https:\/\/datasketches.apache.org\/. (2019). https:\/\/datasketches.apache.org\/"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623669"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511802256"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/214762.214771"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.2970860"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.3390\/e17074918"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451032","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451032","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451032","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451032"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":52,"alternative-id":["10.1145\/3406325.3451032","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451032","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}