{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:02:05Z","timestamp":1757311325180,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0430376"],"award-info":[{"award-number":["CCF-0430376"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-04-1-0735"],"award-info":[{"award-number":["N00014-04-1-0735"]}],"id":[{"id":"10.13039\/100000006","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":[[2009,10]]},"abstract":"<jats:p>In many data mining and machine learning problems, the data items that need to be clustered or classified are not arbitrary points in a high-dimensional space, but are distributions, that is, points on a high-dimensional simplex. For distributions, natural measures are not \u2113<jats:sub><jats:italic>p<\/jats:italic><\/jats:sub>distances, but information-theoretic measures such as the Kullback-Leibler and Hellinger divergences. Similarly, quantities such as the entropy of a distribution are more natural than frequency moments. Efficient estimation of these quantities is a key component in algorithms for manipulating distributions. Since the datasets involved are typically massive, these algorithms need to have only sublinear complexity in order to be feasible in practice.<\/jats:p><jats:p>We present a range of sublinear-time algorithms in various oracle models in which the algorithm accesses the data via an oracle that supports various queries. In particular, we answer a question posed by Batu et al. on testing whether two distributions are close in an information-theoretic sense given independent samples. We then present optimal algorithms for estimating various information-divergences and entropy with a more powerful oracle called the combined oracle that was also considered by Batu et al. Finally, we consider sublinear-space algorithms for these quantities in the data-stream model. In the course of doing so, we explore the relationship between the aforementioned oracle models and the data-stream model. This continues work initiated by Feigenbaum et al. An important additional component to the study is considering data streams that are ordered randomly rather than just those which are ordered adversarially.<\/jats:p>","DOI":"10.1145\/1597036.1597038","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Sublinear estimation of entropy and information distances"],"prefix":"10.1145","volume":"5","author":[{"given":"Sudipto","family":"Guha","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suresh","family":"Venkatasubramanian","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,11,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1111\/j.2517-6161.1966.tb00626.x","article-title":"A general class of coefficients of divergence of one distribution from another","volume":"28","author":"Ali S. M.","year":"1966","journal-title":"J. Royal Statist. Soc. Series B"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"volume-title":"Differential-Geometrical Methods in Statistics","author":"Amari S.","key":"e_1_2_1_3_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5056-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1046920.1194902"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380810"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403645"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796548"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_16"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 328--335","year":"2007","author":"Chakrabarti A.","key":"e_1_2_1_10_1"},{"volume-title":"Statistical decision rules and optimal inference. Transl. Math. Monographs","author":"\u010cencov N. N.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_15"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications. John Wiley&amp;Sons New York. Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications. John Wiley&amp;Sons New York.","DOI":"10.1002\/0471200611"},{"volume-title":"Why least squares and maximum entropy&amp;quest","year":"2032","author":"Csisz\u00e1r I.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the European Symposium on Algorithms. 348--360","author":"Demaine E. D.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944973"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0959-4"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 79--88","author":"Gilbert A. C.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the Internet Measurement Conference. 345--350","author":"Gu Y.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142390"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394623"},{"volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS). 169--176","year":"2007","author":"Guha S.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109637"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Henzinger M. R. Raghavan P. and Rajagopalan S. 1999. Computing on data streams. In External Memory Algorithms 107--118. Henzinger M. R. Raghavan P. and Rajagopalan S. 1999. Computing on data streams. In External Memory Algorithms 107--118.","DOI":"10.1090\/dimacs\/050\/05"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195155"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.255"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140277.1140295"},{"key":"e_1_2_1_29_1","unstructured":"Liese F. and Vajda F. 1987. Convex statistical distances. Teubner-Texte zur Mathematik Band 95 Leipzig. Liese F. and Vajda F. 1987. Convex statistical distances. Teubner-Texte zur Mathematik Band 95 Leipzig."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"volume-title":"Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing. 368--377","author":"Tishby N.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850703"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/WETICE.2005.35"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080091.1080112"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1597036.1597038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:10Z","timestamp":1750249090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1597036.1597038"],"URL":"https:\/\/doi.org\/10.1145\/1597036.1597038","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2006-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}