{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T03:30:30Z","timestamp":1782790230589,"version":"3.54.5"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p>System operators are often interested in extracting different feature streams from multi-dimensional data streams; and reporting their distributions at regular intervals, including the heavy hitters that contribute to the tail portion of the feature distribution. Satisfying these requirements to increase data rates with limited resources is challenging. This paper presents the design and implementation of Panakos that makes the best use of available resources to report a given feature's distribution accurately, its tail contributors, and other stream statistics (e.g., cardinality, entropy, etc.). Our key idea is to leverage the skewness inherent to most feature streams in the real world. We leverage this skewness by disentangling the feature stream into hot, warm, and cold items based on their feature values. We then use different data structures for tracking objects in each category. Panakos provides solid theoretical guarantees and achieves high performance for various tasks. We have implemented Panakos on both software and hardware and compared Panakos to other state-of-the-art sketches using synthetic and real-world datasets. The experimental results demonstrate that Panakos often achieves one order of magnitude better accuracy than the state-of-the-art solutions for a given memory budget.<\/jats:p>","DOI":"10.14778\/3583140.3583147","type":"journal-article","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T16:45:59Z","timestamp":1682009159000},"page":"1291-1304","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Panakos: Chasing the Tails for Multidimensional Data Streams"],"prefix":"10.14778","volume":"16","author":[{"given":"Fuheng","family":"Zhao","sequence":"first","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Punnal Ismail","family":"Khan","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divyakant","family":"Agrawal","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amr El","family":"Abbadi","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arpit","family":"Gupta","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zaoxing","family":"Liu","sequence":"additional","affiliation":[{"name":"Boston University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,4,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Anonymized Internet Traces","year":"2015","unstructured":"[n.d.]. Anonymized Internet Traces 2015 . https:\/\/catalog.caida.org\/details\/dataset\/passive_2015_pcap. Accessed: 2022-10-5. [n.d.]. Anonymized Internet Traces 2015. https:\/\/catalog.caida.org\/details\/dataset\/passive_2015_pcap. Accessed: 2022-10-5."},{"key":"e_1_2_1_2_1","unstructured":"Manos Antonakakis Tim April Michael Bailey Matt Bernhard Elie Bursztein Jaime Cochran Zakir Durumeric J Alex Halderman Luca Invernizzi Michalis Kallitsis etal 2017. Understanding the mirai botnet. In 26th USENIX security symposium (USENIX Security 17). 1093--1110.  Manos Antonakakis Tim April Michael Bailey Matt Bernhard Elie Bursztein Jaime Cochran Zakir Durumeric J Alex Halderman Luca Invernizzi Michalis Kallitsis et al. 2017. Understanding the mirai botnet. In 26th USENIX security symposium (USENIX Security 17). 1093--1110."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035928"},{"key":"e_1_2_1_4_1","volume-title":"Mathematical statistics: basic ideas and selected topics, volumes I-II package","author":"Bickel Peter J","unstructured":"Peter J Bickel and Kjell A Doksum . 2015. Mathematical statistics: basic ideas and selected topics, volumes I-II package . Chapman and Hall\/CRC. Peter J Bickel and Kjell A Doksum. 2015. Mathematical statistics: basic ideas and selected topics, volumes I-II package. Chapman and Hall\/CRC."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656877.2656890"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486011"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2010.06.018"},{"key":"e_1_2_1_8_1","first-page":"421","article-title":"Sulla determinazione empirica delle leggi di probabilita","volume":"4","author":"Cantelli Francesco Paolo","year":"1933","unstructured":"Francesco Paolo Cantelli . 1933 . Sulla determinazione empirica delle leggi di probabilita . Giorn. Ist. Ital. Attuari 4 , 421 - 424 (1933). Francesco Paolo Cantelli. 1933. Sulla determinazione empirica delle leggi di probabilita. Giorn. Ist. Ital. Attuari 4, 421-424 (1933).","journal-title":"Giorn. Ist. Ital. Attuari"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335230"},{"key":"e_1_2_1_10_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Charikar Moses","unstructured":"Moses Charikar , Kevin Chen , and Martin Farach-Colton . 2002. Finding frequent items in data streams . In International Colloquium on Automata, Languages, and Programming . Springer , 693--703. Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming. Springer, 693--703."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939785"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872787"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454225"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM, 44--55","author":"Cormode Graham","year":"2005","unstructured":"Graham Cormode and Shan Muthukrishnan . 2005 . Summarizing and mining skewed data streams . In Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM, 44--55 . Graham Cormode and Shan Muthukrishnan. 2005. Summarizing and mining skewed data streams. In Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM, 44--55."},{"key":"e_1_2_1_16_1","volume-title":"Mathematical methods of statistics","author":"Cram\u00e9r Harald","unstructured":"Harald Cram\u00e9r . 1999. Mathematical methods of statistics . Vol. 43 . Princeton university press . Harald Cram\u00e9r. 1999. Mathematical methods of statistics. Vol. 43. Princeton university press."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872838"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/2346806"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740658"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2010.2043151"},{"key":"e_1_2_1_22_1","volume-title":"Bohatei: Flexible and Elastic {DDoS} Defense. In 24th USENIX security symposium (USENIX Security 15). 817--832.","author":"Fayaz Seyed K","year":"2015","unstructured":"Seyed K Fayaz , Yoshiaki Tobioka , Vyas Sekar , and Michael Bailey . 2015 . Bohatei: Flexible and Elastic {DDoS} Defense. In 24th USENIX security symposium (USENIX Security 15). 817--832. Seyed K Fayaz, Yoshiaki Tobioka, Vyas Sekar, and Michael Bailey. 2015. Bohatei: Flexible and Elastic {DDoS} Defense. In 24th USENIX security symposium (USENIX Security 15). 817--832."},{"key":"e_1_2_1_23_1","volume-title":"Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio 1","author":"Freitag Michael","year":"2019","unstructured":"Michael Freitag and Thomas Neumann . 2019. Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio 1 ( 2019 ), 1--39. Michael Freitag and Thomas Neumann. 2019. Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio 1 (2019), 1--39."},{"key":"e_1_2_1_24_1","volume-title":"Vatsal Sharan, and Peter Bailis.","author":"Gan Edward","year":"2018","unstructured":"Edward Gan , Jialin Ding , Kai Sheng Tai , Vatsal Sharan, and Peter Bailis. 2018 . Moment-based quantile sketches for efficient high cardinality aggregation queries. arXiv preprint arXiv:1803.01969 (2018). Edward Gan, Jialin Ding, Kai Sheng Tai, Vatsal Sharan, and Peter Bailis. 2018. Moment-based quantile sketches for efficient high cardinality aggregation queries. arXiv preprint arXiv:1803.01969 (2018)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233340"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.59929"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/07069328X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230555"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3164135.3164145"},{"key":"e_1_2_1_31_1","volume-title":"https:\/\/barefootnetworks.com\/products\/brief-tofino\/. [Online","author":"Tofino Barefoot","year":"2022","unstructured":"Intel. 2022. Barefoot Tofino . https:\/\/barefootnetworks.com\/products\/brief-tofino\/. [Online ; accessed 19- July - 2022 ]. Intel. 2022. Barefoot Tofino. https:\/\/barefootnetworks.com\/products\/brief-tofino\/. [Online; accessed 19-July-2022]."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.3390\/s22249612"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3359989.3365433"},{"key":"e_1_2_1_34_1","volume-title":"Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs)","author":"Karnin Zohar","unstructured":"Zohar Karnin , Kevin Lang , and Edo Liberty . 2016. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs) . IEEE , 71--78. Zohar Karnin, Kevin Lang, and Edo Liberty. 2016. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs). IEEE, 71--78."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.3390\/electronics8070779"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1012888.1005709"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140103.1140295"},{"key":"e_1_2_1_39_1","volume-title":"2017 International Symposium on Signals, Circuits and Systems (ISSCS). IEEE, 1--5.","author":"Lavric Alexandru","year":"2017","unstructured":"Alexandru Lavric and Valentin Popa . 2017 . Internet of things and LoRa\u2122 low-power wide-area networks: a survey . In 2017 International Symposium on Signals, Circuits and Systems (ISSCS). IEEE, 1--5. Alexandru Lavric and Valentin Popa. 2017. Internet of things and LoRa\u2122 low-power wide-area networks: a survey. In 2017 International Symposium on Signals, Circuits and Systems (ISSCS). IEEE, 1--5."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934906"},{"key":"e_1_2_1_41_1","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Liu Zaoxing","year":"2021","unstructured":"Zaoxing Liu , Hun Namkung , Georgios Nikolaidis , Jeongkeun Lee , Changhoon Kim , Xin Jin , Vladimir Braverman , Minlan Yu , and Vyas Sekar . 2021 . Jaqen: A {High-Performance} {Switch-Native} Approach for Detecting and Mitigating Volumetric {DDoS} Attacks with Programmable Switches . In 30th USENIX Security Symposium (USENIX Security 21) . 3829--3846. Zaoxing Liu, Hun Namkung, Georgios Nikolaidis, Jeongkeun Lee, Changhoon Kim, Xin Jin, Vladimir Braverman, Minlan Yu, and Vyas Sekar. 2021. Jaqen: A {High-Performance} {Switch-Native} Approach for Detecting and Mitigating Volumetric {DDoS} Attacks with Programmable Switches. In 30th USENIX Security Symposium (USENIX Security 21). 3829--3846."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555380"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276342"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 11th international conference on Extending database technology: Advances in database technology. 618--629","author":"Metwally Ahmed","year":"2008","unstructured":"Ahmed Metwally , Divyakant Agrawal , and Amr El Abbadi . 2008 . Why go logarithmic if we can go linear? Towards effective distinct counting of search traffic . In Proceedings of the 11th international conference on Extending database technology: Advances in database technology. 618--629 . Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2008. Why go logarithmic if we can go linear? Towards effective distinct counting of search traffic. In Proceedings of the 11th international conference on Extending database technology: Advances in database technology. 618--629."},{"key":"e_1_2_1_45_1","volume-title":"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 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 International conference on database theory. Springer, 398--412."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/867576"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098829"},{"key":"e_1_2_1_48_1","volume-title":"Improved Utility Analysis of Private CountSketch. arXiv preprint arXiv:2205.08397","author":"Pagh Rasmus","year":"2022","unstructured":"Rasmus Pagh and Mikkel Thorup . 2022. Improved Utility Analysis of Private CountSketch. arXiv preprint arXiv:2205.08397 ( 2022 ). Rasmus Pagh and Mikkel Thorup. 2022. Improved Utility Analysis of Private CountSketch. arXiv preprint arXiv:2205.08397 (2022)."},{"key":"e_1_2_1_49_1","first-page":"78","article-title":"Information and the accuracy attainable in the estimation of statistical parameters","volume":"20","author":"Rao C Radhakrishna","year":"1945","unstructured":"C Radhakrishna Rao . 1945 . Information and the accuracy attainable in the estimation of statistical parameters . Reson. J. Sci. Educ 20 (1945), 78 -- 90 . C Radhakrishna Rao. 1945. Information and the accuracy attainable in the estimation of statistical parameters. Reson. J. Sci. Educ 20 (1945), 78--90.","journal-title":"Reson. J. Sci. Educ"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 6th ACM SIGCOMM conference on Internet measurement. 15--26","author":"Ribeiro Bruno","year":"2006","unstructured":"Bruno Ribeiro , Don Towsley , Tao Ye , and Jean C Bolot . 2006 . Fisher information of sampled packets: an application to flow size estimation . In Proceedings of the 6th ACM SIGCOMM conference on Internet measurement. 15--26 . Bruno Ribeiro, Don Towsley, Tao Ye, and Jean C Bolot. 2006. Fisher information of sampled packets: an application to flow size estimation. In Proceedings of the 6th ACM SIGCOMM conference on Internet measurement. 15--26."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.481776"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882948"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3050220.3063772"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386367.3432729"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183759"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465312"},{"key":"e_1_2_1_58_1","volume-title":"A new sketch method for measuring host connection degree distribution","author":"Wang Pinghui","year":"2014","unstructured":"Pinghui Wang , Xiaohong Guan , Junzhou Zhao , Jing Tao , and Tao Qin . 2014. A new sketch method for measuring host connection degree distribution . IEEE transactions on information forensics and security 9, 6 ( 2014 ), 948--960. Pinghui Wang, Xiaohong Guan, Junzhou Zhao, Jing Tao, and Tao Qin. 2014. A new sketch method for measuring host connection degree distribution. IEEE transactions on information forensics and security 9, 6 (2014), 948--960."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78925"},{"key":"e_1_2_1_60_1","volume-title":"On the convergence properties of the EM algorithm. The Annals of statistics","author":"Jeff Wu CF","year":"1983","unstructured":"CF Jeff Wu . 1983. On the convergence properties of the EM algorithm. The Annals of statistics ( 1983 ), 95--103. CF Jeff Wu. 1983. On the convergence properties of the EM algorithm. The Annals of statistics (1983), 95--103."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230544"},{"key":"e_1_2_1_63_1","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)","author":"Yu Minlan","year":"2013","unstructured":"Minlan Yu , Lavanya Jose , and Rui Miao . 2013 . Software {Defined} {Traffic} Measurement with {OpenSketch} . In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13) . 29--42. Minlan Yu, Lavanya Jose, and Rui Miao. 2013. Software {Defined} {Traffic} Measurement with {OpenSketch}. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 29--42."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452296.3472892"},{"key":"e_1_2_1_65_1","volume-title":"Amr El Abbadi, and Ahmed Metwally","author":"Zhao Fuheng","year":"2021","unstructured":"Fuheng Zhao , Divyakant Agrawal , Amr El Abbadi, and Ahmed Metwally . 2021 . SpaceSaving\u00b1: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded Deletion Model . arXiv preprint arXiv:2112.03462 (2021). Fuheng Zhao, Divyakant Agrawal, Amr El Abbadi, and Ahmed Metwally. 2021. SpaceSaving\u00b1: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded Deletion Model. arXiv preprint arXiv:2112.03462 (2021)."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450990"},{"key":"e_1_2_1_67_1","volume-title":"Amr El Abbadi, and Yu-Xiang Wang","author":"Zhao Fuheng","year":"2022","unstructured":"Fuheng Zhao , Dan Qiao , Rachel Redberg , Divyakant Agrawal , Amr El Abbadi, and Yu-Xiang Wang . 2022 . Differentially private linear sketches: Efficient implementations and applications. arXiv preprint arXiv:2205.09873 (2022). Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. 2022. Differentially private linear sketches: Efficient implementations and applications. arXiv preprint arXiv:2205.09873 (2022)."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183726"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787483"},{"key":"e_1_2_1_70_1","volume-title":"Human behavior and the principle of least effort: An introduction to human ecology","author":"Zipf George Kingsley","unstructured":"George Kingsley Zipf . 2016. Human behavior and the principle of least effort: An introduction to human ecology . Ravenio Books . George Kingsley Zipf. 2016. Human behavior and the principle of least effort: An introduction to human ecology. Ravenio Books."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3583140.3583147","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T16:52:19Z","timestamp":1682009539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3583140.3583147"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2]]},"references-count":69,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.14778\/3583140.3583147"],"URL":"https:\/\/doi.org\/10.14778\/3583140.3583147","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,2]]},"assertion":[{"value":"2023-04-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}