{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T14:24:34Z","timestamp":1784643874305,"version":"3.55.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["3119\/21"],"award-info":[{"award-number":["3119\/21"]}]},{"name":"Technion HPI research school"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Stream monitoring is fundamental in many data stream applications, such as financial data trackers, security, anomaly detection, and load balancing. In that respect, quantiles are of particular interest, as they often capture the user's utility. For example, if a video connection has high tail (e.g., 99'th percentile) latency, the perceived quality will suffer, even if the average and median latencies are low.<\/jats:p>\n          <jats:p>In this work, we consider the problem of approximating the per-item quantiles. Elements in our stream are (ID, value) tuples, and we wish to track the quantiles for each ID. Existing quantile sketches are designed for a plain number stream (i.e., containing just a value). While one could allocate a separate sketch instance for each ID, this may require an infeasible amount of memory. Instead, we consider tracking the quantiles for the heavy hitters (most frequent items), which are often considered particularly important, without knowing them beforehand.<\/jats:p>\n          <jats:p>We first present a couple of simple and effective algorithms that serve as baselines, a sampling approach and a sketching approach. Then, we present SQUAD, an algorithm that combines sampling and sketching while improving the asymptotic space complexity. Intuitively, SQUAD uses a background sampling process to capture the behaviour of the quantiles of an item before it is allocated with a sketch, thereby allowing us to use fewer samples and sketches. The algorithms are rigorously analyzed, and we demonstrate SQUAD's superiority using extensive~simulations on real-world traces.<\/jats:p>","DOI":"10.1145\/3588937","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-25","source":"Crossref","is-referenced-by-count":12,"title":["Together is Better: Heavy Hitters Quantile Estimation"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9254-8529","authenticated-orcid":false,"given":"Rana","family":"Shahout","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6460-9665","authenticated-orcid":false,"given":"Roy","family":"Friedman","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0196-9190","authenticated-orcid":false,"given":"Ran","family":"Ben Basat","sequence":"additional","affiliation":[{"name":"University College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Handling elephant flow on a dpdk-based load balancer - https:\/\/dpdksummitapac2021.sched.com\/event\/hdlm\/handling-elephant-flow-on-a-dpdk-based-load-balancer."},{"key":"e_1_2_2_2_1","unstructured":"Open source code. https:\/\/anonymous.4open.science\/r\/squad-3BB9."},{"key":"e_1_2_2_3_1","unstructured":"The Network Simulator ns-3. https:\/\/www.nsnam.org\/research\/wns3\/wns3--2015\/."},{"key":"e_1_2_2_4_1","volume-title":"Mergeable summaries. ACM Transactions on Database Systems (TODS), 38(4):1--28","author":"Agarwal Pankaj K","year":"2013","unstructured":"Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. ACM Transactions on Database Systems (TODS), 38(4):1--28, 2013."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851192"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3131365.3131407"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230718.3230729"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASCOT.2018.8611241"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.23919\/IFIPNetworking46909.2019.8999467"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211890.3211919"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057216"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098832"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405894"},{"key":"e_1_2_2_15_1","volume-title":"Spanner: Google's Globally Distributed Database. ACM Transactions on Computer Systems, 31(3), aug","author":"Corbett James C.","year":"2013","unstructured":"James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google's Globally Distributed Database. ACM Transactions on Computer Systems, 31(3), aug 2013."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0172-z"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458323"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007588"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142389"},{"key":"e_1_2_2_21_1","unstructured":"Graham Cormode and Pavel Vesel"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387650"},{"key":"e_1_2_2_23_1","first-page":"205","volume-title":"Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles, SOSP","author":"DeCandia Giuseppe","year":"2007","unstructured":"Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon's Highly Available Key-Value Store. In Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles, SOSP, page 205--220, 2007."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24024-4_12"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015495"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a014"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066227"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055597"},{"key":"e_1_2_2_30_1","first-page":"253","volume-title":"SODA","volume":"3","author":"Gupta Anupam","year":"2003","unstructured":"Anupam Gupta and Francis Zane. Counting inversions in lists. In SODA, volume 3, pages 253--254, 2003."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989401"},{"key":"e_1_2_2_32_1","volume-title":"Streaming quantiles algorithms with small space and update time. arXiv preprint arXiv:1907.00236","author":"Ivkin Nikita","year":"2019","unstructured":"Nikita Ivkin, Edo Liberty, Kevin Lang, Zohar Karnin, and Vladimir Braverman. Streaming quantiles algorithms with small space and update time. arXiv preprint arXiv:1907.00236, 2019."},{"key":"e_1_2_2_33_1","first-page":"71","volume-title":"Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs)","author":"Karnin Zohar","year":"2016","unstructured":"Zohar Karnin, Kevin Lang, and Edo Liberty. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs), pages 71--78. IEEE, 2016."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3484266.3487366"},{"key":"e_1_2_2_36_1","volume-title":"Reservoir-sampling algorithms of time complexity o (n (1 log (n\/n))). ACM Transactions on Mathematical Software (TOMS), 20(4):481--493","author":"Li Kim-Hung","year":"1994","unstructured":"Kim-Hung Li. Reservoir-sampling algorithms of time complexity o (n (1 log (n\/n))). ACM Transactions on Mathematical Software (TOMS), 20(4):481--493, 1994."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342076"},{"key":"e_1_2_2_38_1","volume-title":"SRECon","author":"Liz Fong-Jones Kristina Bennett","year":"2018","unstructured":"Kristina Bennett Liz Fong-Jones and Stephen Thorne. Developing Effective Service Level Indicators and Service Level Objectives. In SRECon, 2018."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0424-7"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276342"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304204"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9974-0"},{"key":"e_1_2_2_43_1","volume-title":"Strange Loop Conference","author":"McKinley Kathryn","year":"2017","unstructured":"Kathryn McKinley. Measuring and optimizing tail latency. In Strange Loop Conference, 2017. https:\/\/www.youtube. com\/watch?v=_Zoa3xkzgFk."},{"key":"e_1_2_2_44_1","first-page":"398","volume-title":"International Conference on Database Theory","author":"Metwally Ahmed","year":"2005","unstructured":"Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Efficient computation of frequent and top-k elements in data streams. In International Conference on Database Theory, pages 398--412. Springer, 2005."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/867576"},{"key":"e_1_2_2_46_1","volume-title":"Selection and sorting with limited storage. Theoretical computer science, 12(3):315--323","author":"Ian Munro J","year":"1980","unstructured":"J Ian Munro and Mike S Paterson. Selection and sorting with limited storage. Theoretical computer science, 12(3):315--323, 1980."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098829"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452520.1452553"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787472"},{"key":"e_1_2_2_50_1","volume-title":"Velocity Web Performance and Operations Conference","author":"Schurman Eric","year":"2009","unstructured":"Eric Schurman and Jake Brutlag. Performance related changes and their user impact. In Velocity Web Performance and Operations Conference, 2009. https:\/\/www.youtube.com\/watch?v=bQSE51-gr2s."},{"key":"e_1_2_2_51_1","first-page":"39","volume-title":"The Annals of Statistics","author":"Serffing Robert J","year":"1974","unstructured":"Robert J Serffing. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, pages 39--48, 1974."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_2_53_1","unstructured":"The P4.org Applications Working Group. In-band Network Telemetry (INT) Dataplane Specification. https:\/\/github.com\/p4lang\/p4-applications\/blob\/master\/docs\/telemetry_report.pdf."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21852-6_3"},{"key":"e_1_2_2_55_1","volume-title":"Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1):37--57","author":"Vitter Jeffrey S","year":"1985","unstructured":"Jeffrey S Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1):37--57, 1985."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9584-4"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321601"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.145"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588937","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588937"],"URL":"https:\/\/doi.org\/10.1145\/3588937","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}