{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:29:33Z","timestamp":1750307373172,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T00:00:00Z","timestamp":1275350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["EIA-98-02068"],"award-info":[{"award-number":["EIA-98-02068"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>\n            We describe a simple algorithm for approximating the empirical entropy of a stream of\n            <jats:italic>m<\/jats:italic>\n            values up to a multiplicative factor of (1+\u03f5) using a single pass,\n            <jats:italic>O<\/jats:italic>\n            (\u03f5\n            <jats:sup>\u22122<\/jats:sup>\n            log (\u03b4\n            <jats:sup>\u22121<\/jats:sup>\n            ) log\n            <jats:italic>m<\/jats:italic>\n            ) words of space, and\n            <jats:italic>O<\/jats:italic>\n            (log \u03f5\n            <jats:sup>\u22121<\/jats:sup>\n            + log log \u03b4\n            <jats:sup>\u22121<\/jats:sup>\n            + log log\n            <jats:italic>m<\/jats:italic>\n            ) processing time per item in the stream. Our algorithm is based upon a novel extension of a method introduced by Alon et al. [1999]. This improves over previous work on this problem. We show a space lower bound of \u03a9(\u03f5\n            <jats:sup>\u22122<\/jats:sup>\n            \/log\n            <jats:sup>2<\/jats:sup>\n            (\u03f5\n            <jats:sup>\u22121<\/jats:sup>\n            )), demonstrating that our algorithm is near-optimal in terms of its dependency on \u03f5.\n          <\/jats:p>\n          <jats:p>\n            We show that generalizing to multiplicative-approximation of the\n            <jats:italic>k<\/jats:italic>\n            th-order entropy requires close to linear space for\n            <jats:italic>k<\/jats:italic>\n            \u22651. In contrast we show that additive-approximation is possible in a single pass using only poly-logarithmic space. Lastly, we show how to compute a multiplicative approximation to the entropy of a random walk on an undirected graph.\n          <\/jats:p>","DOI":"10.1145\/1798596.1798604","type":"journal-article","created":{"date-parts":[[2010,6,29]],"date-time":"2010-06-29T13:02:22Z","timestamp":1277816542000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["A near-optimal algorithm for estimating the entropy of a stream"],"prefix":"10.1145","volume":"6","author":[{"given":"Amit","family":"Chakrabarti","sequence":"first","affiliation":[{"name":"Dartmouth College, Hanover, NH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"AT&amp;T Research, Park Avenue, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Mcgregor","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,7,2]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1006\/jcss.1997.1545"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1055558.1055598"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 633--634","author":"Babcock B.","unstructured":"Babcock , B. , Datar , M. , and Motwani , R . 2002. Sampling from a moving window over streaming data . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 633--634 . Babcock, B., Datar, M., and Motwani, R. 2002. Sampling from a moving window over streaming data. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 633--634.","key":"e_1_2_1_3_1"},{"volume-title":"Proceedings of the International Workshop on Randomization and Approximation Techniques (RANDOM). 1--10","author":"Bar-Yossef Z.","unstructured":"Bar-Yossef , Z. , Jayram , T. S. , Kumar , R. , Sivakumar , D. , and Trevisan , L . 2002a. Counting distinct elements in a data stream . In Proceedings of the International Workshop on Randomization and Approximation Techniques (RANDOM). 1--10 . Bar-Yossef, Z., Jayram, T. S., Kumar, R., Sivakumar, D., and Trevisan, L. 2002a. Counting distinct elements in a data stream. In Proceedings of the International Workshop on Randomization and Approximation Techniques (RANDOM). 1--10.","key":"e_1_2_1_4_1"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 623--632","author":"Bar-Yossef Z.","unstructured":"Bar-Yossef , Z. , Kumar , R. , and Sivakumar , D . 2002b. Reductions in streaming algorithms, with an application to counting triangles in graphs . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 623--632 . Bar-Yossef, Z., Kumar, R., and Sivakumar, D. 2002b. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 623--632.","key":"e_1_2_1_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1137\/S0097539702403645"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/11841036_16"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.5555\/1109557.1109634"},{"volume-title":"Proceedings of the International Colloquium on Structural Information Complexity. 33--42","author":"Bose P.","unstructured":"Bose , P. , Kranakis , E. , Morin , P. , and Tang , Y . 2003. Bounds for frequency estimation of packet streams . In Proceedings of the International Colloquium on Structural Information Complexity. 33--42 . Bose, P., Kranakis, E., Morin, P., and Tang, Y. 2003. Bounds for frequency estimation of packet streams. In Proceedings of the International Colloquium on Structural Information Complexity. 33--42.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 328--335","author":"Chakrabarti A.","year":"2007","unstructured":"Chakrabarti , A. , Cormode , G. , and McGregor , A. 2007 . A near-optimal algorithm for computing the entropy of a stream . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 328--335 . Chakrabarti, A., Cormode, G., and McGregor, A. 2007. A near-optimal algorithm for computing the entropy of a stream. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 328--335."},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1007\/11672142_15"},{"volume-title":"Proceedings of the Annual IEEE Conference on Computational Complexity (CCC). 107--117","author":"Chakrabarti A.","unstructured":"Chakrabarti , A. , Khot , S. , and Sun , X . 2003. Near-Optimal lower bounds on the multi-party communication complexity of set disjointness . In Proceedings of the Annual IEEE Conference on Computational Complexity (CCC). 107--117 . Chakrabarti, A., Khot, S., and Sun, X. 2003. Near-Optimal lower bounds on the multi-party communication complexity of set disjointness. In Proceedings of the Annual IEEE Conference on Computational Complexity (CCC). 107--117.","key":"e_1_2_1_12_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1016\/j.jalgor.2003.12.001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1065167.1065201"},{"doi-asserted-by":"crossref","unstructured":"Cover T. and Thomas J. 1991. Elements of Information Theory. John Wiley and Sons.   Cover T. and Thomas J. 1991. Elements of Information Theory. John Wiley and Sons.","key":"e_1_2_1_15_1","DOI":"10.1002\/0471200611"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Datar M.","unstructured":"Datar , M. , Gionis , A. , Indyk , P. , and Motwani , R . 2002. Maintaining stream statistics over sliding windows . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Datar, M., Gionis, A., Indyk, P., and Motwani, R. 2002. Maintaining stream statistics over sliding windows. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1016\/j.tcs.2005.09.013"},{"unstructured":"Ganguly S. A hybrid algorithm for estimating frequency moments of data streams. Unpublished manuscript http:\/\/www.cse.iitk.ac.in\/users\/sganguly\/HybridFk.pdf.  Ganguly S. A hybrid algorithm for estimating frequency moments of data streams. Unpublished manuscript http:\/\/www.cse.iitk.ac.in\/users\/sganguly\/HybridFk.pdf.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/564870.564880"},{"volume-title":"Proceedings of the Internet Measurement Conference.","author":"Gu Y.","unstructured":"Gu , Y. , McCallum , A. , and Towsley , D . 2005. Detecting anomalies in network traffic using maximum entropy estimation . In Proceedings of the Internet Measurement Conference. Gu, Y., McCallum, A., and Towsley, D. 2005. Detecting anomalies in network traffic using maximum entropy estimation. In Proceedings of the Internet Measurement Conference.","key":"e_1_2_1_20_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/1109557.1109637"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/FOCS.2008.76"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1006\/jagm.2000.1131"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 283--289","author":"Indyk P.","unstructured":"Indyk , P. and Woodruff , D. P . 2003. Tight lower bounds for the distinct elements problem . In Proceedings of the IEEE Symposium on Foundations of Computer Science. 283--289 . Indyk, P. and Woodruff, D. P. 2003. Tight lower bounds for the distinct elements problem. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 283--289.","key":"e_1_2_1_24_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/1060590.1060621"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/1140277.1140295"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1016\/0167-6423(82)90012-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/3147.3165"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1109\/WETICE.2005.35"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 167--175","author":"Woodruff D. P.","year":"2004","unstructured":"Woodruff , D. P. 2004 . Optimal space lower bounds for all frequency moments . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 167--175 . Woodruff, D. P. 2004. Optimal space lower bounds for all frequency moments. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 167--175."},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/1080091.1080112"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1798596.1798604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1798596.1798604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:58Z","timestamp":1750245778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1798596.1798604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1798596.1798604"],"URL":"https:\/\/doi.org\/10.1145\/1798596.1798604","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,6]]},"assertion":[{"value":"2007-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}