{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:00Z","timestamp":1750220460001,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T00:00:00Z","timestamp":1636934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF 1947789, CCF 1725543, CSR 1763680, CCF 1716252, CCF 1617618, CNS 1938709, CCF 2106827, CCF 1715777, CCF 2118832, AitF 1637458"],"award-info":[{"award-number":["CCF 1947789, CCF 1725543, CSR 1763680, CCF 1716252, CCF 1617618, CNS 1938709, CCF 2106827, CCF 1715777, CCF 2118832, AitF 1637458"]}]},{"name":"Laboratory-Directed Research-and-Development program at Sandia National Laboratories"},{"name":"National Technology and Engineering Solutions of Sandia, LLC."},{"name":"Honeywell International, Inc."},{"name":"U.S. Department of Energy\u2019s National Nuclear Security Administration","award":["DE-NA0003525"],"award-info":[{"award-number":["DE-NA0003525"]}]},{"name":"U.S. Department of Energy or the United States Government"},{"DOI":"10.13039\/100006192","name":"Advanced Scientific Computing Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006192","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Office of Science of the DOE"},{"DOI":"10.13039\/100017223","name":"NERSC","doi-asserted-by":"crossref","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100017223","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Exascale Computing Project","award":["17-SC-20-SC"],"award-info":[{"award-number":["17-SC-20-SC"]}]},{"name":"U.S. Department of Energy Office of Science and the National Nuclear Security Administration"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            Given an input stream\n            <jats:italic>S<\/jats:italic>\n            of size\n            <jats:italic>N<\/jats:italic>\n            , a\n            <jats:italic>\n              <jats:bold>\u0278-heavy hitter<\/jats:bold>\n            <\/jats:italic>\n            is an item that occurs at least\n            <jats:italic>\u0278N<\/jats:italic>\n            times in\n            <jats:italic>S<\/jats:italic>\n            . The problem of finding heavy-hitters is extensively studied in the database literature.\n          <\/jats:p>\n          <jats:p>\n            We study a real-time heavy-hitters variant in which an element must be reported shortly after we see its T = \u0278 N-th occurrence (and hence it becomes a heavy hitter). We call this the Timely Event Detection (\n            <jats:sc>TED<\/jats:sc>\n            ) Problem. The\n            <jats:sc>TED<\/jats:sc>\n            problem models the needs of many real-world monitoring systems, which demand accurate (i.e., no false negatives) and timely reporting of all events from large, high-speed streams with a low reporting threshold (high sensitivity).\n          <\/jats:p>\n          <jats:p>\n            Like the classic heavy-hitters problem, solving the\n            <jats:sc>TED<\/jats:sc>\n            problem without false-positives requires large space (\u03a9 (N) words). Thus in-RAM heavy-hitters algorithms typically sacrifice accuracy (i.e., allow false positives), sensitivity, or timeliness (i.e., use multiple passes).\n          <\/jats:p>\n          <jats:p>\n            We show how to adapt heavy-hitters algorithms to external memory to solve the\n            <jats:sc>TED<\/jats:sc>\n            problem on large high-speed streams while guaranteeing accuracy, sensitivity, and timeliness. Our data structures are limited only by I\/O-bandwidth (not latency) and support a tunable tradeoff between reporting delay and I\/O overhead. With a small bounded reporting delay, our algorithms incur only a logarithmic I\/O overhead.\n          <\/jats:p>\n          <jats:p>We implement and validate our data structures empirically using the Firehose streaming benchmark. Multi-threaded versions of our structures can scale to process 11M observations per second before becoming CPU bound. In comparison, a naive adaptation of the standard heavy-hitters algorithm to external memory would be limited by the storage device\u2019s random I\/O throughput, i.e., \u2248100K observations per second.<\/jats:p>","DOI":"10.1145\/3472392","type":"journal-article","created":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T17:48:45Z","timestamp":1636998525000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Timely Reporting of Heavy Hitters Using External Memory"],"prefix":"10.1145","volume":"46","author":[{"given":"Shikha","family":"Singh","sequence":"first","affiliation":[{"name":"Williams College, Williamstown, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prashant","family":"Pandey","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratories and University of California Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Bender","sequence":"additional","affiliation":[{"name":"Stony Brook University, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan W.","family":"Berry","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas M.","family":"Kroeger","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cynthia A.","family":"Phillips","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,15]]},"reference":[{"key":"e_1_3_2_2_2","article-title":"Zipf, Power Law, Pareto: A ranking tutorial. HP Research","author":"Adamic L. A.","year":"2008","unstructured":"L. A. Adamic. 2008. Zipf, Power Law, Pareto: A ranking tutorial. HP Research. Retrieved from http:\/\/www.hpl.hp.com\/research\/idl\/papers\/ranking\/ranking.html.","journal-title":"http:\/\/www.hpl.hp.com\/research\/idl\/papers\/ranking\/ranking.html"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_5_2","article-title":"FireHose Benchmarking Streaming Architectures","author":"Anderson Karl","year":"2016","unstructured":"Karl Anderson. 2016. FireHose Benchmarking Streaming Architectures. Retrieved July 9, 2021 from https:\/\/www.clsac.org\/uploads\/5\/0\/6\/3\/50633811\/anderson-clsac-2016.pdf.","journal-title":"https:\/\/www.clsac.org\/uploads\/5\/0\/6\/3\/50633811\/anderson-clsac-2016.pdf"},{"key":"e_1_3_2_6_2","article-title":"FireHose Streaming Benchmarks","author":"Anderson Karl","year":"2013","unstructured":"Karl Anderson and Steve Plimpton. 2013. FireHose Streaming Benchmarks. Retrieved December 11, 2018 from https:\/\/github.com\/stream-benchmarking\/firehose.","journal-title":"https:\/\/github.com\/stream-benchmarking\/firehose"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/603867.603884"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218843099000150"},{"key":"e_1_3_2_9_2","volume-title":"Drinking Water Treatment Source Water Warly Warning System State of the Science Review","author":"Bartrand Tim","year":"2017","unstructured":"Tim Bartrand, Walter Grayman, and Terra Haxton. 2017. Drinking Water Treatment Source Water Warly Warning System State of the Science Review. Technical Report EPA\/600\/R-17\/405."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524364"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.2172\/1528756"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323210"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"issue":"5","key":"e_1_3_2_14_2","first-page":"22","article-title":"An introduction to B-trees and write-optimization","volume":"40","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-trees and write-optimization. :login; mag. 40, 5 (Oct. 2015), 22\u201328.","journal-title":":login; mag."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056117"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304214"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902284"},{"key":"e_1_3_2_20_2","first-page":"33","volume-title":"Proceedings of the 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201903)","author":"Bose Prosenjit","year":"2003","unstructured":"Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang. 2003. Bounds for frequency estimation of packet streams. In Proceedings of the 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201903). 33\u201342."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-94-011-3488-0_5","volume-title":"Automated Reasoning","author":"Boyer Robert S.","year":"1991","unstructured":"Robert S. Boyer and J. Strother Moore. 1991. MJRTY\u2014A fast majority vote algorithm. In Automated Reasoning. Springer, 105\u2013117."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034798"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897558"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873718"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644201"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/338219.338650"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287388"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_3_2_32_2","first-page":"39:1\u201339:14","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Conway Alex","year":"2018","unstructured":"Alex Conway, Martin Farach-Colton, and Philip Shilane. 2018. Optimal hashing in external memory. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918). 39:1\u201339:14."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0172-z"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24698-5_7"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061325"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740658"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1341431.1341433"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671338"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315264"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375664"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065211"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095164"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2006.355"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.16"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3098954.3098992"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/MPAE.2006.1632456"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1177080.1177102"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287400"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/1929820.1929831"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0382-5"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.5555\/867576"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380598"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2013.04.014"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183759"},{"key":"e_1_3_2_61_2","volume-title":"Proceedings of the Network and Distributed Systems Security Symposium (NDSS\u201905)","author":"Venkataraman Shobha","year":"2005","unstructured":"Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, and Avrim Blum. 2005. New streaming algorithms for fast detection of superspreaders. In Proceedings of the Network and Distributed Systems Security Symposium (NDSS\u201905)."},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/CATCH.2009.28"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2933868"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-010-0053-5"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3472392","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3472392","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3472392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:10Z","timestamp":1750193290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3472392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,15]]},"references-count":63,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3472392"],"URL":"https:\/\/doi.org\/10.1145\/3472392","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2021,11,15]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}