{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:40Z","timestamp":1763468020343,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T00:00:00Z","timestamp":1286841600000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>\n            The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case guarantees on real data. This leads to the question of whether some stronger bounds can be guaranteed. We answer this in the positive by showing that a class of counter-based algorithms (including the popular and very space-efficient\n            <jats:sc>Frequent<\/jats:sc>\n            and\n            <jats:sc>SpacesSaving<\/jats:sc>\n            algorithms) provides much stronger approximation guarantees than previously known. Specifically, we show that errors in the approximation of individual elements do not depend on the frequencies of the most frequent elements, but only on the frequency of the remaining tail. This shows that counter-based methods are the most space-efficient (in fact, space-optimal) algorithms having this strong error bound.\n          <\/jats:p>\n          <jats:p>\n            This tail guarantee allows these algorithms to solve the sparse recovery problem. Here, the goal is to recover a faithful representation of the vector of frequencies,\n            <jats:italic>f<\/jats:italic>\n            . We prove that using space\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ), the algorithms construct an approximation\n            <jats:italic>f<\/jats:italic>\n            * to the frequency vector\n            <jats:italic>f<\/jats:italic>\n            so that the\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            error \u2225\u2225\n            <jats:italic>f<\/jats:italic>\n            \u2212\u2225\n            <jats:italic>f<\/jats:italic>\n            *\u2225\n            <jats:sub>1<\/jats:sub>\n            is close to the best possible error min\n            <jats:sub>\n              <jats:italic>f<\/jats:italic>\n              \u2032\n            <\/jats:sub>\n            \u2225\n            <jats:italic>f<\/jats:italic>\n            \u2032 \u2212\n            <jats:italic>f<\/jats:italic>\n            \u2225\n            <jats:sub>1<\/jats:sub>\n            , where\n            <jats:italic>f\u2032<\/jats:italic>\n            ranges over all vectors with at most\n            <jats:italic>k<\/jats:italic>\n            non-zero entries. This improves the previously best known space bound of about\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) for streams without element deletions (where\n            <jats:italic>n<\/jats:italic>\n            is the size of the domain from which stream elements are drawn). Other consequences of the tail guarantees are results for skewed (Zipfian) data, and guarantees for accuracy of merging multiple summarized streams.\n          <\/jats:p>","DOI":"10.1145\/1862919.1862923","type":"journal-article","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T15:55:04Z","timestamp":1292860504000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Space-optimal heavy hitters with strong error bounds"],"prefix":"10.1145","volume":"35","author":[{"given":"Radu","family":"Berinde","sequence":"first","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Indyk","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,10,12]]},"reference":[{"volume-title":"Proceedings of the 9th DBPL International Confenrence on Data Base and Programming Languages. 1--11","author":"Arasu A.","key":"e_1_2_1_1_1","unstructured":"Arasu , A. , Babu , S. , and Widom , J . 2003. CQL: A language for continuous queries over streams and relations . In Proceedings of the 9th DBPL International Confenrence on Data Base and Programming Languages. 1--11 . Arasu, A., Babu, S., and Widom, J. 2003. CQL: A language for continuous queries over streams and relations. In Proceedings of the 9th DBPL International Confenrence on Data Base and Programming Languages. 1--11."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559819"},{"volume-title":"Proceedings of the Allerton Conference.","author":"Berinde R.","key":"e_1_2_1_3_1","unstructured":"Berinde , R. , Gilbert , A. , Indyk , P. , Karloff , H. , and Strauss , M . 2008a. Combining geometry and combinatorics: a unified approach to sparse signal recovery . In Proceedings of the Allerton Conference. Berinde, R., Gilbert, A., Indyk, P., Karloff, H., and Strauss, M. 2008a. Combining geometry and combinatorics: a unified approach to sparse signal recovery. In Proceedings of the Allerton Conference."},{"volume-title":"Proceedings of the Allerton Conference.","author":"Berinde R.","key":"e_1_2_1_4_1","unstructured":"Berinde , R. , Indyk , P. , and Ruzic , M . 2008b. Practical near-optimal sparse recovery in the l 1 norm . In Proceedings of the Allerton Conference. Berinde, R., Indyk, P., and Ruzic, M. 2008b. Practical near-optimal sparse recovery in the l 1 norm. In Proceedings of the Allerton Conference."},{"key":"e_1_2_1_5_1","unstructured":"Bestavros A. Crovella M. and Taqqu T. 1999. Heavy-Tailed Probability Distributions in the World Wide Web. Birkh\u00e4user 3--25.   Bestavros A. Crovella M. and Taqqu T. 1999. Heavy-Tailed Probability Distributions in the World Wide Web. Birkh\u00e4user 3--25."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304214"},{"volume-title":"Proceedings of the 2nd IEEE MDM International Conference on Mobile Data Management. 3--14","author":"Bonnet P.","key":"e_1_2_1_7_1","unstructured":"Bonnet , P. , Gehrke , J. , and Seshadri , P . 2001. Towards sensor database systems . In Proceedings of the 2nd IEEE MDM International Conference on Mobile Data Management. 3--14 . Bonnet, P., Gehrke, J., and Seshadri, P. 2001. Towards sensor database systems. In Proceedings of the 2nd IEEE MDM International Conference on Mobile Data Management. 3--14."},{"volume-title":"Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity. 33--42","author":"Bose P.","key":"e_1_2_1_8_1","unstructured":"Bose , P. , Kranakis , E. , Morin , P. , and Tang , Y . 2003. Bounds for frequency estimation of packet streams . In Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity. 33--42 . Bose, P., Kranakis, E., Morin, P., and Tang, Y. 2003. Bounds for frequency estimation of packet streams. In Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity. 33--42."},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 126--134","author":"Breslau L.","key":"e_1_2_1_9_1","unstructured":"Breslau , L. , Cao , P. , Fan , L. , Phillips , G. , and Shenker , S . 1999. Web caching and Zipf-like distributions: Evidence and implications . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 126--134 . Breslau, L., Cao, P., Fan, L., Phillips, G., and Shenker, S. 1999. Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 126--134."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","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. 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."},{"volume-title":"Proceedings of the 29th ICALP International Colloqium on Automata, Languages and Programming. 693--703","author":"Charikar M.","key":"e_1_2_1_12_1","unstructured":"Charikar , M. , Chen , K. , and Farach-Colton , M . 2002. Finding frequent items in data streams . In Proceedings of the 29th ICALP International Colloqium on Automata, Languages and Programming. 693--703 . Charikar, M., Chen, K., and Farach-Colton, M. 2002. Finding frequent items in data streams. In Proceedings of the 29th ICALP International Colloqium on Automata, Languages and Programming. 693--703."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559895"},{"key":"e_1_2_1_14_1","first-page":"1530","article-title":"Finding frequent items in data streams","volume":"1","author":"Cormode G.","year":"2008","unstructured":"Cormode , G. and Hadjieleftheriou , M. 2008 . Finding frequent items in data streams . VLDB J. 1 , 2, 1530 -- 1541 . Cormode, G. and Hadjieleftheriou, M. 2008. Finding frequent items in data streams. VLDB J. 1, 2, 1530--1541.","journal-title":"VLDB J."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 464--475","author":"Cormode G.","key":"e_1_2_1_15_1","unstructured":"Cormode , G. , Korn , F. , Muthukrishnan , S. , and Srivastava , D . 2003. Finding hierarchical heavy hitters in data streams . In Proceedings of the International Conference on Very Large Data Bases. 464--475 . Cormode, G., Korn, F., Muthukrishnan, S., and Srivastava, D. 2003. Finding hierarchical heavy hitters in data streams. In Proceedings of the International Conference on Very Large Data Bases. 464--475."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"volume-title":"Proceedings of the 10th ESA Annual European Symposium on Algorithms. 348--360","author":"Demaine E.","key":"e_1_2_1_17_1","unstructured":"Demaine , E. , Ortiz , A. L. , and Munro , J . 2002. Frequency estimation of internet packet streams with limited space . In Proceedings of the 10th ESA Annual European Symposium on Algorithms. 348--360 . Demaine, E., Ortiz, A. L., and Munro, J. 2002. Frequency estimation of internet packet streams with limited space. In Proceedings of the 10th ESA Annual European Symposium on Algorithms. 348--360."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/505202.505212"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 299--310","author":"Fang M.","key":"e_1_2_1_20_1","unstructured":"Fang , M. , Shivakumar , N. , Garcia-Molina , H. , Motwani , R. , and Ullman , J . 1998. Computing iceberg queries efficiently . In Proceedings of the International Conference on Very Large Data Bases. 299--310 . Fang, M., Shivakumar, N., Garcia-Molina, H., Motwani, R., and Ullman, J. 1998. Computing iceberg queries efficiently. In Proceedings of the International Conference on Very Large Data Bases. 299--310."},{"volume-title":"Frequent itemset mining dataset repository","author":"Repository","key":"e_1_2_1_21_1","unstructured":"FIMI Repository . 2008. Frequent itemset mining dataset repository , University of Helsinki . http:\/\/fimi.cs.helsinki.fi\/data. FIMI Repository. 2008. Frequent itemset mining dataset repository, University of Helsinki. http:\/\/fimi.cs.helsinki.fi\/data."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_16"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564794"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250824"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375664"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065211"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_2_1_28_1","unstructured":"Indyk P. 2007. Sketching streaming and sublinear-space algorithms. Graduate course notes. http:\/\/stellar.mit.edu\/S\/course\/6\/fa07\/6.895\/.  Indyk P. 2007. Sketching streaming and sublinear-space algorithms. Graduate course notes. http:\/\/stellar.mit.edu\/S\/course\/6\/fa07\/6.895\/."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.82"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/380995.381033"},{"volume-title":"Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI).","author":"Lucchese C.","key":"e_1_2_1_32_1","unstructured":"Lucchese , C. , Orlando , S. , Perego , R. , and Silvestri , F . 2004. Webdocs: a real-life huge transactional dataset . In Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI). Lucchese, C., Orlando, S., Perego, R., and Silvestri, F. 2004. Webdocs: a real-life huge transactional dataset. In Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2008.11.001"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 346--357","author":"Manku G.","key":"e_1_2_1_34_1","unstructured":"Manku , G. and Motwani , R . 2002. Approximate frequency counts over data streams . In Proceedings of the International Conference on Very Large Data Bases. 346--357 . Manku, G. and Motwani, R. 2002. Approximate frequency counts over data streams. In Proceedings of the International Conference on Very Large Data Bases. 346--357."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"volume-title":"How popular is your paper&quest","author":"Redner S.","key":"e_1_2_1_38_1","unstructured":"Redner , S. 1998. How popular is your paper&quest ; An empirical study of the citation distribution. European Physical J. B , 131--134. Redner, S. 1998. How popular is your paper&quest; An empirical study of the citation distribution. European Physical J. B, 131--134."},{"key":"e_1_2_1_39_1","unstructured":"Rice DSP Group. Compressed sensing resources. http:\/\/www.dsp.ece.rice.edu\/cs.  Rice DSP Group. Compressed sensing resources. http:\/\/www.dsp.ece.rice.edu\/cs."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"volume-title":"Human Behavior and The Principle of Least Effort","author":"Zipf G.","key":"e_1_2_1_41_1","unstructured":"Zipf , G. 1949. Human Behavior and The Principle of Least Effort . Addison-Wesley . Zipf, G. 1949. Human Behavior and The Principle of Least Effort. Addison-Wesley."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862923","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1862919.1862923","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:51Z","timestamp":1750281291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862923"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,12]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1145\/1862919.1862923"],"URL":"https:\/\/doi.org\/10.1145\/1862919.1862923","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2010,10,12]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}