{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:32Z","timestamp":1750307732381,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2009,3,23]],"date-time":"2009-03-23T00:00:00Z","timestamp":1237766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2009,3,23]]},"DOI":"10.1145\/1514894.1514928","type":"proceedings-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:53Z","timestamp":1239035693000},"page":"284-295","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["The average-case complexity of counting distinct elements"],"prefix":"10.1145","author":[{"given":"David P.","family":"Woodruff","sequence":"first","affiliation":[{"name":"IBM Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,3,23]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"ACM SIGMOD\/PODS Workshop on Management and Processing of Data Streams (MPDS) FCRC","author":"Akella A.","year":"2003","unstructured":"A. Akella , A. Bharambe , M. Reiter , and S. Seshan . Detecting DDoS attacks on ISP networks . In ACM SIGMOD\/PODS Workshop on Management and Processing of Data Streams (MPDS) FCRC , 2003 . A. Akella, A. Bharambe, M. Reiter, and S. Seshan. Detecting DDoS attacks on ISP networks. In ACM SIGMOD\/PODS Workshop on Management and Processing of Data Streams (MPDS) FCRC, 2003."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_3_1","volume-title":"The Probabilistic Method","author":"Alon N.","year":"1992","unstructured":"N. Alon and J. Spencer . The Probabilistic Method . John Wiley , 1992 . N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 1992."},{"key":"e_1_3_2_1_5_1","first-page":"1","volume-title":"RANDOM","author":"Bar-Yossef Z.","year":"2002","unstructured":"Z. Bar-Yossef , T. S. Jayram , R. Kumar , D. Sivakumar , and L. Trevisan . Counting distinct elements in a data stream . In RANDOM , pages 1 -- 10 , 2002 . Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. Counting distinct elements in a data stream. In RANDOM, pages 1--10, 2002."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1137\/S0097539702403645"},{"key":"e_1_3_2_1_7_1","volume-title":"Manuscript","author":"Bunge J.","year":"2007","unstructured":"J. Bunge . Bibliography on estimating the number of classes in a population . Manuscript , 2007 . J. Bunge. Bibliography on estimating the number of classes in a population. Manuscript, 2007."},{"key":"e_1_3_2_1_8_1","volume-title":"Yes, the GIGP really does work - and is workable! JASIS, 44(2):61--69","author":"Burrell Q. L.","year":"1993","unstructured":"Q. L. Burrell and M. R. Fenton . Yes, the GIGP really does work - and is workable! JASIS, 44(2):61--69 , 1993 . Q. L. Burrell and M. R. Fenton. Yes, the GIGP really does work - and is workable! JASIS, 44(2):61--69, 1993."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/1374376.1374470"},{"key":"e_1_3_2_1_10_1","first-page":"720","volume-title":"SODA","author":"Chakrabarti A.","year":"2008","unstructured":"A. Chakrabarti , T. S. Jayram , and M. P\u01cetra\u015fcu . Tight lower bounds for selection in randomly ordered streams . In SODA , pages 720 -- 729 , 2008 . A. Chakrabarti, T. S. Jayram, and M. P\u01cetra\u015fcu. Tight lower bounds for selection in randomly ordered streams. In SODA, pages 720--729, 2008."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/335168.335230"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.5555\/646255.684566"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1137\/1.9781611972757.5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.5555\/129837"},{"unstructured":"W. Feller. An Introduction to Probability Theory and its Applications volume 1. John Wiley and Sons 3 edition 1968.  W. Feller. An Introduction to Probability Theory and its Applications volume 1. John Wiley and Sons 3 edition 1968.","key":"e_1_3_2_1_15_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1016\/0022-0000(85)90041-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.5555\/314500.315083"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1145\/581751.581753"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/1142351.1142390"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.5555\/2394539.2394623"},{"key":"e_1_3_2_1_21_1","first-page":"169","volume-title":"AISTATS","author":"Guha S.","year":"2007","unstructured":"S. Guha and A. Mcgregor . Space-efficient sampling . In AISTATS , pages 169 -- 176 , 2007 . S. Guha and A. Mcgregor. Space-efficient sampling. In AISTATS, pages 169--176, 2007."},{"key":"e_1_3_2_1_22_1","volume-title":"Manuscript","author":"Jayram T. S.","year":"2007","unstructured":"T. S. Jayram , R. Kumar , and D. Sivakumar . The one-way communication complexity of gap hamming distance . Manuscript , 2007 . T. S. Jayram, R. Kumar, and D. Sivakumar. The one-way communication complexity of gap hamming distance. Manuscript, 2007."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1002\/rsa.3240070105"},{"key":"e_1_3_2_1_24_1","volume-title":"IITK Workshop on Algorithms for Data Streams","author":"Kumar R.","year":"2006","unstructured":"R. Kumar . Story of distinct elements . IITK Workshop on Algorithms for Data Streams , 2006 . R. Kumar. Story of distinct elements. IITK Workshop on Algorithms for Data Streams, 2006."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1007\/978-3-540-74208-1_42"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.5555\/264772"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.5555\/1076315"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.5555\/211390"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1137\/1.9781611972962.7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1561\/0400000002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.5555\/1333875.1334226"},{"key":"e_1_3_2_1_32_1","volume-title":"New York: Springer-Verlag","author":"van Lint J. H.","year":"1992","unstructured":"J. H. van Lint . An Introduction to Coding Theory . New York: Springer-Verlag , 1992 . J. H. van Lint. An Introduction to Coding Theory. New York: Springer-Verlag, 1992."},{"key":"e_1_3_2_1_33_1","first-page":"167","volume-title":"SODA","author":"Woodruff D.","year":"2004","unstructured":"D. Woodruff . Optimal space lower bounds for all frequency moments . In SODA , pages 167 -- 175 , 2004 . D. Woodruff. Optimal space lower bounds for all frequency moments. In SODA, pages 167--175, 2004."}],"event":{"acronym":"EDBT\/ICDT '09","name":"EDBT\/ICDT '09: EDBT\/ICDT '09 joint conference","location":"St. Petersburg Russia"},"container-title":["Proceedings of the 12th International Conference on Database Theory"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1514894.1514928","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1514894.1514928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:43Z","timestamp":1750253923000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1514894.1514928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,23]]},"references-count":32,"alternative-id":["10.1145\/1514894.1514928","10.1145\/1514894"],"URL":"https:\/\/doi.org\/10.1145\/1514894.1514928","relation":{},"subject":[],"published":{"date-parts":[[2009,3,23]]},"assertion":[{"value":"2009-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}