{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:02Z","timestamp":1778807822190,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":74,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,15]],"date-time":"2016-06-15T00:00:00Z","timestamp":1465948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Google India PhD Fellowship"],"award-info":[{"award-number":["Google India PhD Fellowship"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Indian Department of Science and Technology","award":["DSTO1358"],"award-info":[{"award-number":["DSTO1358"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,15]]},"DOI":"10.1145\/2902251.2902284","type":"proceedings-article","created":{"date-parts":[[2016,6,16]],"date-time":"2016-06-16T20:16:05Z","timestamp":1466108165000},"page":"385-400","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems"],"prefix":"10.1145","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Palash","family":"Dey","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"IBM Research Almaden, San Jose, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.99"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645920.672836"},{"key":"e_1_3_2_1_3_1","first-page":"1","volume-title":"Proc. 9th International Workshop on Database Programming Languages DBPL","author":"Arasu A.","year":"2003","unstructured":"A. Arasu , S. Babu , and J. Widom . CQL: A language for continuous queries over streams and relations . In Proc. 9th International Workshop on Database Programming Languages DBPL , pages 1 -- 19 , 2003 . A. Arasu, S. Babu, and J. Widom. CQL: A language for continuous queries over streams and relations. In Proc. 9th International Workshop on Database Programming Languages DBPL, pages 1--19, 2003."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.384007"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304214"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361194"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/648058.746944"},{"key":"e_1_3_2_1_9_1","volume-title":"Handbook of computational social choice","author":"Brandt F.","year":"2015","unstructured":"F. Brandt , V. Conitzer , U. Endriss , J. Lang , and A. Procaccia . Handbook of computational social choice , 2015 . F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia. Handbook of computational social choice, 2015."},{"key":"e_1_3_2_1_10_1","volume-title":"BPTree: an l2 heavy hitters algorithm using constant memory","author":"Braverman V.","year":"2016","unstructured":"V. Braverman , S. R. Chestnut , N. Ivkin , J. Nelson , Z. Wang , and D. P. Woodruff . BPTree: an l2 heavy hitters algorithm using constant memory . 2016 . arXiv:1603.00759. V. Braverman, S. R. Chestnut, N. Ivkin, J. Nelson, Z. Wang, and D. P. Woodruff. BPTree: an l2 heavy hitters algorithm using constant memory. 2016. arXiv:1603.00759."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897558"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.005"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148289"},{"key":"e_1_3_2_1_15_1","first-page":"1","volume-title":"Proc. 21st International Teletraffic Congress, ITC","author":"Chabchoub Y.","year":"2009","unstructured":"Y. Chabchoub , C. Fricker , and H. Mohamed . Analysis of a bloom filter algorithm via the supermarket model . In Proc. 21st International Teletraffic Congress, ITC , pages 1 -- 8 , 2009 . Y. Chabchoub, C. Fricker, and H. Mohamed. Analysis of a bloom filter algorithm via the supermarket model. In Proc. 21st International Teletraffic Congress, ITC, pages 1--8, 2009."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064018"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454225"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324172.1324174"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_1_22_1","volume-title":"Elements of information theory","author":"Cover T. M.","year":"2012","unstructured":"T. M. Cover and J. A. Thomas . Elements of information theory . John Wiley & Sons , 2012 . T. M. Cover and J. A. Thomas. Elements of information theory. John Wiley & Sons, 2012."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740658"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2772879.2773334"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0873"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728174"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671338"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934993"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250824"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375664"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/963770.963772"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065211"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304195"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.273716"},{"key":"e_1_3_2_1_37_1","first-page":"2573","volume-title":"Proc. Annual Conference on Neural Information Processing Systems","author":"Jiang A.","year":"2014","unstructured":"A. Jiang , L. S. Marcolino , A. D. Procaccia , T. Sandholm , N. Shah , and M. Tambe . Diverse randomized agents vote to win . In Proc. Annual Conference on Neural Information Processing Systems , pages 2573 -- 2581 , 2014 . A. Jiang, L. S. Marcolino, A. D. Procaccia, T. Sandholm, N. Shah, and M. Tambe. Diverse randomized agents vote to win. In Proc. Annual Conference on Neural Information Processing Systems, pages 2573--2581, 2014."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1057\/9780230305045_7","volume-title":"Political Communication in Britain","author":"Kellner P.","year":"2011","unstructured":"P. Kellner , J. Twyman , and A. Wells . Polling voting intentions . In Political Communication in Britain , pages 94 -- 108 . Springer , 2011 . P. Kellner, J. Twyman, and A. Wells. Polling voting intentions. In Political Communication in Britain, pages 94--108. Springer, 2011."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2006.326"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/264772"},{"key":"e_1_3_2_1_43_1","volume-title":"Apr.","author":"Larsen K. G.","year":"2016","unstructured":"K. G. Larsen , J. Nelson , H. L. Nguyen , and M. Thorup . Heavy hitters via cluster-preserving clustering. arXiv:1604.01357 , Apr. 2016 . K. G. Larsen, J. Nelson, H. L. Nguyen, and M. Thorup. Heavy hitters via cluster-preserving clustering. arXiv:1604.01357, Apr. 2016."},{"key":"e_1_3_2_1_44_1","first-page":"2","article-title":"Introduction to algorithms","volume":"5","author":"Leiserson C. E.","year":"2001","unstructured":"C. E. Leiserson , R. L. Rivest , C. Stein , and T. H. Cormen . Introduction to algorithms . The MIT press , 5 : 2 -- 2 , 2001 . C. E. Leiserson, R. L. Rivest, C. Stein, and T. H. Cormen. Introduction to algorithms. The MIT press, 5:2--2, 2001.","journal-title":"The MIT press"},{"key":"e_1_3_2_1_45_1","first-page":"1","volume-title":"Synthesis Lectures on Human Language Technologies","author":"Li H.","year":"2014","unstructured":"H. Li . Learning to rank for information retrieval and natural language processing . In Synthesis Lectures on Human Language Technologies , volume 7 , pages 1 -- 121 . Morgan & Claypool Publishers , 2014 . H. Li. Learning to rank for information retrieval and natural language processing. In Synthesis Lectures on Human Language Technologies, volume 7, pages 1--121. Morgan & Claypool Publishers, 2014."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2005.08.023"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287400"},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. Fourth Workshop on Human Computation (HCOMP-12)","author":"Mao A.","year":"2012","unstructured":"A. Mao , A. D. Procaccia , and Y. Chen . Social Choice for Human Computation . In Proc. Fourth Workshop on Human Computation (HCOMP-12) , 2012 . A. Mao, A. D. Procaccia, and Y. Chen. Social Choice for Human Computation. In Proc. Fourth Workshop on Human Computation (HCOMP-12), 2012."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2891460.2891619"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005569"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2008.2009071"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"J. S. Moore. J. Algorithm June 1981. p. 208--209.  J. S. Moore. J. Algorithm June 1981. p. 208--209.","DOI":"10.1016\/B978-0-408-00567-8.50010-9"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_3_2_1_58_1","volume-title":"Decision making: Its logic and practice","author":"Mullen D.","year":"1991","unstructured":"D. Mullen and B. Roth . Decision making: Its logic and practice . Savage, MD : Rowman and Littlefield Publishers , Inc., 1991 . D. Mullen and B. Roth. Decision making: Its logic and practice. Savage, MD: Rowman and Littlefield Publishers, Inc., 1991."},{"key":"e_1_3_2_1_59_1","volume-title":"Algorithms and applications","author":"Muthukrishnan S.","year":"2005","unstructured":"S. Muthukrishnan . Data streams : Algorithms and applications . Now Publishers Inc , 2005 . S. Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331049"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2005.03.023"},{"key":"e_1_3_2_1_62_1","first-page":"2104","volume-title":"Proc. 32nd International Conference on Machine Learning (ICML-15)","author":"Prasad A.","year":"2015","unstructured":"A. Prasad , H. Pareek , and P. Ravikumar . Distributional rank aggregation, and an axiomatic analysis . In Proc. 32nd International Conference on Machine Learning (ICML-15) , pages 2104 -- 2112 , 2015 . A. Prasad, H. Pareek, and P. Ravikumar. Distributional rank aggregation, and an axiomatic analysis. In Proc. 32nd International Conference on Machine Learning (ICML-15), pages 2104--2112, 2015."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/245108.245121"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673300"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_3_2_1_66_1","volume-title":"Shannon's information methods for lower bounds for probabilistic communication complexity. Master's thesis","author":"Smirnov D.","year":"1988","unstructured":"D. Smirnov . Shannon's information methods for lower bounds for probabilistic communication complexity. Master's thesis , Moscow University , 1988 . D. Smirnov. Shannon's information methods for lower bounds for probabilistic communication complexity. Master's thesis, Moscow University, 1988."},{"key":"e_1_3_2_1_67_1","first-page":"435","volume-title":"Proc. 18th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015","author":"Sun X.","year":"2015","unstructured":"X. Sun and D. P. Woodruff . Tight bounds for graph problems in insertion streams . In Proc. 18th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015 ), pages 435 -- 448 , 2015 . X. Sun and D. P. Woodruff. Tight bounds for graph problems in insertion streams. In Proc. 18th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015), pages 435--448, 2015."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.5555\/645922.673325"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745779"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2638572"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031241"},{"key":"e_1_3_2_1_72_1","volume-title":"Appeared in ICDT '16","author":"Woodruff D. P.","year":"2016","unstructured":"D. P. Woodruff . New Algorithms for Heavy Hitters in Data Streams . 2016 . arXiv 1603.01733 . Appeared in ICDT '16 . D. P. Woodruff. New Algorithms for Heavy Hitters in Data Streams. 2016. arXiv 1603.01733. Appeared in ICDT '16."},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229086"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"event":{"name":"SIGMOD\/PODS'16: International Conference on Management of Data","location":"San Francisco California USA","acronym":"SIGMOD\/PODS'16","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2902251.2902284","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2902251.2902284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:59Z","timestamp":1750222499000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2902251.2902284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,15]]},"references-count":74,"alternative-id":["10.1145\/2902251.2902284","10.1145\/2902251"],"URL":"https:\/\/doi.org\/10.1145\/2902251.2902284","relation":{},"subject":[],"published":{"date-parts":[[2016,6,15]]},"assertion":[{"value":"2016-06-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}