{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:12Z","timestamp":1759638612155,"version":"3.41.0"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T00:00:00Z","timestamp":1540166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DRDO Frontiers Project","award":["DRDO0687"],"award-info":[{"award-number":["DRDO0687"]}]},{"name":"DST INSPIRE","award":["DST\/INSPIRE\/04\/2016\/001479"],"award-info":[{"award-number":["DST\/INSPIRE\/04\/2016\/001479"]}]},{"name":"DST Ramanujan","award":["DSTO1358"],"award-info":[{"award-number":["DSTO1358"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            We give the first optimal bounds for returning the \u2113\n            <jats:sub>1<\/jats:sub>\n            -heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of\n            <jats:italic>m<\/jats:italic>\n            items in { 1, 2, \u2026 ,\n            <jats:italic>n<\/jats:italic>\n            } and parameters 0 &lt; \u03b5 &lt; \u03c6 \u2a7d 1, let\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            denote the frequency of item\n            <jats:italic>i<\/jats:italic>\n            , i.e., the number of times item\n            <jats:italic>i<\/jats:italic>\n            occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items\n            <jats:italic>i<\/jats:italic>\n            for which\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            \u2a7e \u03c6\n            <jats:italic>m<\/jats:italic>\n            , returns no items\n            <jats:italic>j<\/jats:italic>\n            for which\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \u2a7d (\u03c6 \u2212\u03b5)\n            <jats:italic>m<\/jats:italic>\n            , and returns approximations\n            <jats:italic>f\u02dc<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            with |\n            <jats:italic>f\u02dc<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            \u2212\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            | \u2a7d \u03b5\n            <jats:italic>m<\/jats:italic>\n            for each item\n            <jats:italic>i<\/jats:italic>\n            that it returns. Our algorithm uses\n            <jats:italic>O<\/jats:italic>\n            (\u03b5\n            <jats:sup>\u22121<\/jats:sup>\n            log \u03c6\n            <jats:sup>\u22121<\/jats:sup>\n            + \u03c6\n            <jats:sup>\u22121<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            + log log\n            <jats:italic>m<\/jats:italic>\n            ) bits of space, processes each stream update in\n            <jats:italic>O<\/jats:italic>\n            (1) worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive \u03b5\n            <jats:italic>m<\/jats:italic>\n            error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of \u2113\n            <jats:sub>1<\/jats:sub>\n            -heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.\n          <\/jats:p>","DOI":"10.1145\/3264427","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T12:16:16Z","timestamp":1540296976000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["An Optimal Algorithm for \u2113\n            <sub>1<\/sub>\n            -Heavy Hitters in Insertion Streams and Related Problems"],"prefix":"10.1145","volume":"15","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"CSA Department Indian Institute of Science"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Palash","family":"Dey","sequence":"additional","affiliation":[{"name":"CSE Department IIT Kharagpur, Kharagpur, West Bengal, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"School of Computer Science Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.99"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645920.672836"},{"volume-title":"Proceedings of the 9th International Workshop on Database Programming Languages (DBPL\u201903)","year":"2003","author":"Arasu Arvind","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.384007"},{"volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201902)","author":"Bar-Yossef Ziv","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304214"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361194"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/648058.746944"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Felix Brandt Vincent Conitzer Ulle Endriss J\u00e9r\u00f4me Lang and Ariel Procaccia. 2015. Handbook of Computational Social Choice. Cambridge University Press.  Felix Brandt Vincent Conitzer Ulle Endriss J\u00e9r\u00f4me Lang and Ariel Procaccia. 2015. Handbook of Computational Social Choice. Cambridge University Press.","DOI":"10.1017\/CBO9781107446984.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Vladimir Braverman Stephen R. Chestnut Nikita Ivkin and David P. Woodruff. 2016. Beating countsketch for heavy hitters in insertion streams. Retrieved from http:\/\/arxiv.org\/abs\/1511.00661.  Vladimir Braverman Stephen R. Chestnut Nikita Ivkin and David P. Woodruff. 2016. Beating countsketch for heavy hitters in insertion streams. Retrieved from http:\/\/arxiv.org\/abs\/1511.00661.","DOI":"10.1145\/2897518.2897558"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.005"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148289"},{"volume-title":"Proceedings of the 21st International Teletraffic Congress (ITC\u201909)","year":"2009","author":"Chabchoub Yousra","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064018"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454225"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324172.1324174"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_22_1","unstructured":"Thomas M. Cover and Joy A. Thomas. 2012. Elements of Information Theory. John Wiley 8 Sons.  Thomas M. Cover and Joy A. Thomas. 2012. Elements of Information Theory. John Wiley 8 Sons."},{"volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201902)","author":"Demaine Erik D.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of the 14th International Conference on Autonomous Systems and Multiagent Systems (AAMAS\u201915)","year":"2015","author":"Dey Palash","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201915)","author":"Dey Palash","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728174"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886564"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"volume-title":"Proceedings of 24th International Conference on Very Large Data Bases (VLDB\u201998)","author":"Fang Min","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934993"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250824"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375664"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/963770.963772"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065211"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304195"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.273716"},{"key":"e_1_2_1_38_1","unstructured":"Albert Jiang Leandro Soriano Marcolino Ariel D. Procaccia Tuomas Sandholm Nisarg Shah and Milind Tambe. 2014. Diverse randomized agents vote to win. In Advances in Neural Information Processing Systems. 2573--2581.   Albert Jiang Leandro Soriano Marcolino Ariel D. Procaccia Tuomas Sandholm Nisarg Shah and Milind Tambe. 2014. Diverse randomized agents vote to win. In Advances in Neural Information Processing Systems. 2573--2581."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"volume-title":"Political Communication in Britain","author":"Kellner Peter","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2006.326"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY.   Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_44_1","unstructured":"Kasper Green Larsen Jelani Nelson Huy Le Nguyen and Mikkel Thorup. 2016. Optimal space heavy hitters with fast update and query. Retrieved from http:\/\/ita.ucsd.edu\/workshop\/16\/files\/abstract\/abstract_3738.txt.  Kasper Green Larsen Jelani Nelson Huy Le Nguyen and Mikkel Thorup. 2016. Optimal space heavy hitters with fast update and query. Retrieved from http:\/\/ita.ucsd.edu\/workshop\/16\/files\/abstract\/abstract_3738.txt."},{"key":"e_1_2_1_45_1","unstructured":"Charles E. Leiserson Ronald L. Rivest Clifford Stein and Thomas H. Cormen. 2001. Introduction to algorithms. MIT Press 5 (2001) 2--2.   Charles E. Leiserson Ronald L. Rivest Clifford Stein and Thomas H. Cormen. 2001. Introduction to algorithms. MIT Press 5 (2001) 2--2."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/3019285"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2005.08.023"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287400"},{"volume-title":"Proceedings of the 4th Workshop on Human Computation (HCOMP\u201912)","year":"2012","author":"Mao Andrew","key":"e_1_2_1_50_1"},{"volume-title":"Proceedings of of the 27th Conference on Artificial Intelligence (AAAI\u201913)","year":"2013","author":"Mao Andrew","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005569"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2008.2009071"},{"key":"e_1_2_1_57_1","unstructured":"J. Strother Moore. 1981. J. Algor. (June 1981) 208--209.  J. Strother Moore. 1981. J. Algor. (June 1981) 208--209."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"volume-title":"Decision Making: Its Logic and Practice","year":"1991","author":"Mullen D. J.","key":"e_1_2_1_59_1"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019604"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331049"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2005.03.023"},{"volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915)","year":"2015","author":"Prasad Adarsh","key":"e_1_2_1_63_1"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/245108.245121"},{"volume-title":"Proceedings of 21th International Conference on Very Large Data Bases (VLDB\u201995)","author":"Savasere Ashok","key":"e_1_2_1_65_1"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_67_1","unstructured":"D. Smirnov. 1988. Shannon\u2019s Information Methods for Lower Bounds for Probabilistic Communication Complexity. Master\u2019s thesis. Moscow University.  D. Smirnov. 1988. Shannon\u2019s Information Methods for Lower Bounds for Probabilistic Communication Complexity. Master\u2019s thesis. Moscow University."},{"key":"e_1_2_1_68_1","unstructured":"Xiaoming Sun and David P. Woodruff. 2015. Tight bounds for graph problems in insertion streams. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915). 435--448.  Xiaoming Sun and David P. Woodruff. 2015. Tight bounds for graph problems in insertion streams. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915). 435--448."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/645922.673325"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745779"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2638572"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031241"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229086"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3264427","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3264427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:35Z","timestamp":1750235975000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3264427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,22]]},"references-count":74,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3264427"],"URL":"https:\/\/doi.org\/10.1145\/3264427","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,10,22]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}