{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:45Z","timestamp":1775638485839,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,5,31]],"date-time":"2020-05-31T00:00:00Z","timestamp":1590883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000093","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01GM122935"],"award-info":[{"award-number":["R01GM122935"]}],"id":[{"id":"10.13039\/100000093","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 805476, CCF 822388, CCF 1724745, CCF 1715777, CCF 1637458, IIS 1541613, CRII 1947789, CNS 1408695, CNS 1755615, CCF 1439084, CCF 1725543, CSR 1763680, CCF 1716252, CCF 1617618, CNS 1938709, IIS 1247726"],"award-info":[{"award-number":["CCF 805476, CCF 822388, CCF 1724745, CCF 1715777, CCF 1637458, IIS 1541613, CRII 1947789, CNS 1408695, CNS 1755615, CCF 1439084, CCF 1725543, CSR 1763680, CCF 1716252, CCF 1617618, CNS 1938709, IIS 1247726"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000936","name":"Gordon and Betty Moore Foundation","doi-asserted-by":"publisher","award":["GBMF4554"],"award-info":[{"award-number":["GBMF4554"]}],"id":[{"id":"10.13039\/100000936","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,11]]},"DOI":"10.1145\/3318464.3380598","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T17:12:33Z","timestamp":1590772353000},"page":"1431-1446","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Timely Reporting of Heavy Hitters using External Memory"],"prefix":"10.1145","author":[{"given":"Prashant","family":"Pandey","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shikha","family":"Singh","sequence":"additional","affiliation":[{"name":"Wellesley College, Williamstown, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Bender","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan W.","family":"Berry","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas M.","family":"Kroeger","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cynthia A.","family":"Phillips","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"LA Adamic. 2008. Zipf Power law Pareto: a ranking tutorial. HP Research. http:\/\/www.hpl.hp.com\/research\/idl\/papers\/ranking\/ranking.html.  LA Adamic. 2008. Zipf Power law Pareto: a ranking tutorial. HP Research. http:\/\/www.hpl.hp.com\/research\/idl\/papers\/ranking\/ranking.html."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/603867.603884"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218843099000150"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323210"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_3_2_2_10_1","volume-title":"An Introduction to B\u03b5-Trees and Write-Optimization. :login","author":"Bender Michael A.","year":"2015","unstructured":"Michael A. Bender , Martin Farach-Colton , William Jannen , Rob Johnson , Bradley C. Kuszmaul , Donald E. Porter , Jun Yuan , and Yang Zhan . 2015. An Introduction to B\u03b5-Trees and Write-Optimization. :login ; magazine, Vol. 40 , 5 ( October 2015 ), 22--28. Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan. 2015. An Introduction to B\u03b5-Trees and Write-Optimization. :login; magazine, Vol. 40, 5 (October 2015), 22--28."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056117"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-9496(2009)135:4(253)"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304214"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902284"},{"key":"e_1_3_2_2_17_1","unstructured":"Prosenjit Bose Evangelos Kranakis Pat Morin and Yihui Tang. 2003. Bounds for Frequency Estimation of Packet Streams.. In SIROCCO. 33--42.  Prosenjit Bose Evangelos Kranakis Pat Morin and Yihui Tang. 2003. Bounds for Frequency Estimation of Packet Streams.. In SIROCCO. 33--42."},{"key":"e_1_3_2_2_18_1","unstructured":"Robert S Boyer and J Strother Moore. 1981. A fast majority vote algorithm .SRI International. Computer Science Laboratory.  Robert S Boyer and J Strother Moore. 1981. A fast majority vote algorithm .SRI International. Computer Science Laboratory."},{"key":"e_1_3_2_2_19_1","volume-title":"BPTree: an l2 heavy hitters algorithm using constant memory. arXiv preprint arXiv:1603.00759","author":"Braverman Vladimir","year":"2016","unstructured":"Vladimir Braverman , Stephen R Chestnut , Nikita Ivkin , Jelani Nelson , Zhengyu Wang , and David P Woodruff . 2016b. BPTree: an l2 heavy hitters algorithm using constant memory. arXiv preprint arXiv:1603.00759 ( 2016 ). Vladimir Braverman, Stephen R Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P Woodruff. 2016b. BPTree: an l2 heavy hitters algorithm using constant memory. arXiv preprint arXiv:1603.00759 (2016)."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897558"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"e_1_3_2_2_22_1","volume-title":"Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1448--1456","author":"Brodal Gerth St\u00f8lting","unstructured":"Gerth St\u00f8lting Brodal , Erik D. Demaine , Jeremy T. Fineman , John Iacono , Stefan Langerman , and J. Ian Munro . 2010. Cache-Oblivious Dynamic Dictionaries with Update\/Query Tradeoffs . In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1448--1456 . Gerth St\u00f8lting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, and J. Ian Munro. 2010. Cache-Oblivious Dynamic Dictionaries with Update\/Query Tradeoffs. In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1448--1456."},{"key":"e_1_3_2_2_23_1","volume-title":"Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 546--554","author":"Brodal Gerth St\u00f8lting","year":"2003","unstructured":"Gerth St\u00f8lting Brodal and Rolf Fagerberg . 2003 . Lower Bounds for External Memory Dictionaries . In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 546--554 . Gerth St\u00f8lting Brodal and Rolf Fagerberg. 2003. Lower Bounds for External Memory Dictionaries. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 546--554."},{"key":"e_1_3_2_2_24_1","volume-title":"Westbrook","author":"Buchsbaum Adam L.","year":"2000","unstructured":"Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , and Jeffery R . Westbrook . 2000 . On external memory graph traversal. In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 859--860. Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, and Jeffery R. Westbrook. 2000. On external memory graph traversal. In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 859--860."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287388"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_3_2_2_28_1","volume-title":"Cosma Rohilla Shalizi, and Mark EJ Newman","author":"Clauset Aaron","year":"2009","unstructured":"Aaron Clauset , Cosma Rohilla Shalizi, and Mark EJ Newman . 2009 . Power-law distributions in empirical data. SIAM review, Vol. 51 , 4 (2009), 661--703. Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. 2009. Power-law distributions in empirical data. SIAM review, Vol. 51, 4 (2009), 661--703."},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP). 39:1--39:14","author":"Conway Alex","year":"2018","unstructured":"Alex Conway , Martin Farach-Colton , and Philip Shilane . 2018 . Optimal Hashing in External Memory . In Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP). 39:1--39:14 . Alex Conway, Martin Farach-Colton, and Philip Shilane. 2018. Optimal Hashing in External Memory. In Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP). 39:1--39:14."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0172-z"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24698-5_7"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061325"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_33"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341431.1341433"},{"key":"e_1_3_2_2_36_1","volume-title":"Proc. 24rd International Conference on Very Large Databases (VLDB). 299--310","author":"Fang Min","year":"1998","unstructured":"Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , and Jeffrey D Ullman . 1998 . Computing Iceberg Queries Efficiently .. In Proc. 24rd International Conference on Very Large Databases (VLDB). 299--310 . Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D Ullman. 1998. Computing Iceberg Queries Efficiently.. In Proc. 24rd International Conference on Very Large Databases (VLDB). 299--310."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315264"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375664"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065211"},{"key":"e_1_3_2_2_40_1","volume-title":"Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 570--582","author":"Iacono John","unstructured":"John Iacono and Mihai Pua tracs cu. 2012. Using hashing to solve the dictionary problem . In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 570--582 . John Iacono and Mihai Pua tracs cu. 2012. Using hashing to solve the dictionary problem. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 570--582."},{"key":"e_1_3_2_2_41_1","volume-title":"http:\/\/firehose.sandia.gov\/. [Online","author":"Karl Anderson Steve Plimpton","year":"2015","unstructured":"Steve Plimpton Karl Anderson . 2013. FireHose. http:\/\/firehose.sandia.gov\/. [Online ; accessed 19- Dec- 2015 ]. Steve Plimpton Karl Anderson. 2013. FireHose. http:\/\/firehose.sandia.gov\/. [Online; accessed 19-Dec-2015]."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2006.355"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.16"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098954.3098992"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/MPAE.2006.1632456"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1177080.1177102"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"key":"e_1_3_2_2_49_1","volume-title":"Proc. 19th USENIX Conference on Security .","author":"Meiners Chad R.","unstructured":"Chad R. Meiners , Jignesh Patel , Eric Norige , Eric Torng , and Alex X. Liu . 2010. Fast Regular Expression Matching Using Small TCAMs for Network Intrusion Detection and Prevention Systems . In Proc. 19th USENIX Conference on Security . Chad R. Meiners, Jignesh Patel, Eric Norige, Eric Torng, and Alex X. Liu. 2010. Fast Regular Expression Matching Using Small TCAMs for Network Intrusion Detection and Prevention Systems. In Proc. 19th USENIX Conference on Security ."},{"key":"e_1_3_2_2_50_1","volume-title":"Proc. International Conference on Database Theory. Springer, 398--412","author":"Metwally Ahmed","year":"2005","unstructured":"Ahmed Metwally , Divyakant Agrawal , and Amr El Abbadi . 2005 . Efficient computation of frequent and top-k elements in data streams . In Proc. International Conference on Database Theory. Springer, 398--412 . Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2005. Efficient computation of frequent and top-k elements in data streams. In Proc. International Conference on Database Theory. Springer, 398--412."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/867576"},{"key":"e_1_3_2_2_52_1","volume-title":"Pareto distributions and Zipf's law. Contemporary physics","author":"Newman Mark EJ","year":"2005","unstructured":"Mark EJ Newman . 2005. Power laws , Pareto distributions and Zipf's law. Contemporary physics , Vol. 46 , 5 ( 2005 ), 323--351. Mark EJ Newman. 2005. Power laws, Pareto distributions and Zipf's law. Contemporary physics, Vol. 46, 5 (2005), 323--351."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2013.04.014"},{"key":"e_1_3_2_2_56_1","volume-title":"Phillip B. Gibbons, and Avrim Blum.","author":"Venkataraman Shobha","year":"2005","unstructured":"Shobha Venkataraman , Dawn Xiaodong Song , Phillip B. Gibbons, and Avrim Blum. 2005 . New Streaming Algorithms for Fast Detection of Superspreaders. Department of Electrical and Computing Engineering . Shobha Venkataraman, Dawn Xiaodong Song, Phillip B. Gibbons, and Avrim Blum. 2005. New Streaming Algorithms for Fast Detection of Superspreaders. Department of Electrical and Computing Engineering ."},{"key":"e_1_3_2_2_57_1","volume-title":"Extensible Monitoring System. In 2009 Cybersecurity Applications Technology Conference for Homeland Security. 212--223","author":"Yan H.","year":"2009","unstructured":"H. Yan , R. Oliveira , K. Burnett , D. Matthews , L. Zhang , and D. Massey . 2009. BGPmon: A Real-Time, Scalable , Extensible Monitoring System. In 2009 Cybersecurity Applications Technology Conference for Homeland Security. 212--223 . https:\/\/doi.org\/10.1109\/CATCH. 2009 .28 H. Yan, R. Oliveira, K. Burnett, D. Matthews, L. Zhang, and D. Massey. 2009. BGPmon: A Real-Time, Scalable, Extensible Monitoring System. In 2009 Cybersecurity Applications Technology Conference for Homeland Security. 212--223. https:\/\/doi.org\/10.1109\/CATCH.2009.28"}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA","acronym":"SIGMOD\/PODS '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3380598","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3318464.3380598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:23Z","timestamp":1750199903000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3380598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,31]]},"references-count":55,"alternative-id":["10.1145\/3318464.3380598","10.1145\/3318464"],"URL":"https:\/\/doi.org\/10.1145\/3318464.3380598","relation":{},"subject":[],"published":{"date-parts":[[2020,5,31]]},"assertion":[{"value":"2020-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}