{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T14:24:32Z","timestamp":1784643872918,"version":"3.55.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p>\n            Recording the frequency of items in highly skewed data streams is a fundamental and hot problem in recent years. The literature demonstrates that\n            <jats:italic>sketch<\/jats:italic>\n            is the most promising solution. The typical metrics to measure a sketch are accuracy and speed, but existing sketches make only trade-offs between the two dimensions. Our proposed solution is a new sketch framework called Stingy sketch with two key techniques: Bit-pinching Counter Tree (\n            <jats:bold>BCTree<\/jats:bold>\n            ) and Prophet Queue (\n            <jats:bold>PQueue<\/jats:bold>\n            ) which optimizes both the accuracy and speed. The key idea of\n            <jats:bold>BCTree<\/jats:bold>\n            is to split a large fixed-size counter into many small nodes of a tree structure, and to use a precise encoding to perform carry-in operations with low processing overhead. The key idea of\n            <jats:bold>PQueue<\/jats:bold>\n            is to use pipelined prefetch technique to make most memory accesses happen in L2 cache without losing precision. Importantly, the two techniques are cooperative so that Stingy sketch can improve accuracy and speed simultaneously. Extensive experimental results show that Stingy sketch is up to 50% more accurate than the SOTA of accuracy-oriented sketches and is up to 33% faster than the SOTA of speed-oriented sketches.\n          <\/jats:p>","DOI":"10.14778\/3523210.3523220","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:21Z","timestamp":1655936601000},"page":"1426-1438","source":"Crossref","is-referenced-by-count":53,"title":["Stingy sketch"],"prefix":"10.14778","volume":"15","author":[{"given":"Haoyu","family":"Li","sequence":"first","affiliation":[{"name":"Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qizhi","family":"Chen","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yixin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tong","family":"Yang","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Cui","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"254","volume-title":"CoNEXT","author":"Ben-Basat Ran","year":"2018","unstructured":"Ran Ben-Basat , Gil Einziger , Isaac Keslassy , Ariel Orda , Shay Vargaftik , and Erez Waisbard . Memento : making sliding windows efficient for heavy hitters . In CoNEXT , pages 254 -- 266 . ACM, 2018 . Ran Ben-Basat, Gil Einziger, Isaac Keslassy, Ariel Orda, Shay Vargaftik, and Erez Waisbard. Memento: making sliding windows efficient for heavy hitters. In CoNEXT, pages 254--266. ACM, 2018."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM41043.2020.9155340"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00080"},{"key":"e_1_2_1_4_1","volume-title":"the 24th ACM SIGKDD International Conference","author":"Tong Y.","year":"2018","unstructured":"Y. Tong , J. Gong , H. Zhang , Z. Lei , and X. Li . Heavyguardian: Separate and guard hot items in data streams . In the 24th ACM SIGKDD International Conference , 2018 . Y. Tong, J. Gong, H. Zhang, Z. Lei, and X. Li. Heavyguardian: Separate and guard hot items in data streams. In the 24th ACM SIGKDD International Conference, 2018."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183759"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403208"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452802"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452840"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3458456"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452829"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457327"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452833"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330825"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00048"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24698-5_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_2_1_18_1","first-page":"63","volume-title":"RIDE","author":"Cheng Kai","year":"2005","unstructured":"Kai Cheng , Limin Xiang , Mizuho Iwaihara , Haiyan Xu , and Mukesh K. Mohania . Time-decaying bloom filters for data streams with skewed distributions . In RIDE , pages 63 -- 69 . IEEE Computer Society , 2005 . Kai Cheng, Limin Xiang, Mizuho Iwaihara, Haiyan Xu, and Mukesh K. Mohania. Time-decaying bloom filters for data streams with skewed distributions. In RIDE, pages 63--69. IEEE Computer Society, 2005."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137652"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2923772"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2192447"},{"key":"e_1_2_1_22_1","first-page":"1449","volume-title":"SIGMOD Conference","author":"Roy Pratanu","year":"2016","unstructured":"Pratanu Roy , Arijit Khan , and Gustavo Alonso . Augmented sketch : Faster and more accurate stream processing . In SIGMOD Conference , pages 1449 -- 1463 . ACM, 2016 . Pratanu Roy, Arijit Khan, and Gustavo Alonso. Augmented sketch: Faster and more accurate stream processing. In SIGMOD Conference, pages 1449--1463. ACM, 2016."},{"key":"e_1_2_1_23_1","volume-title":"Apache flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 36(4)","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone , Asterios Katsifodimos , Stephan Ewen , Volker Markl , Seif Haridi , and Kostas Tzoumas . Apache flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 36(4) , 2015 . Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. Apache flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 36(4), 2015."},{"key":"e_1_2_1_24_1","first-page":"1093","volume-title":"EMNLP-CoNLL","author":"Goyal Amit","year":"2012","unstructured":"Amit Goyal , Hal Daum\u00e9 III, and Graham Cormode . Sketch algorithms for estimating point queries in NLP . In EMNLP-CoNLL , pages 1093 -- 1103 . ACL, 2012 . Amit Goyal, Hal Daum\u00e9 III, and Graham Cormode. Sketch algorithms for estimating point queries in NLP. In EMNLP-CoNLL, pages 1093--1103. ACL, 2012."},{"key":"e_1_2_1_25_1","first-page":"193","volume-title":"Proc. VLDB Endow.","author":"Zhao Peixiang","year":"2011","unstructured":"Peixiang Zhao , Charu C. Aggarwal , and Min Wang . gsketch : On query estimation in graph streams . Proc. VLDB Endow. , pages 193 -- 204 , 2011 . Peixiang Zhao, Charu C. Aggarwal, and Min Wang. gsketch: On query estimation in graph streams. Proc. VLDB Endow., pages 193--204, 2011."},{"key":"e_1_2_1_26_1","first-page":"26","volume-title":"IEEE Data Eng. Bull.","author":"Kollios George","year":"2005","unstructured":"George Kollios , John W. Byers , Jeffrey Considine , Marios Hadjieleftheriou , and Feifei Li . Robust aggregation in sensor networks . IEEE Data Eng. Bull. , pages 26 -- 32 , 2005 . George Kollios, John W. Byers, Jeffrey Considine, Marios Hadjieleftheriou, and Feifei Li. Robust aggregation in sensor networks. IEEE Data Eng. Bull., pages 26--32, 2005."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems","author":"Dittmann Gero","year":"2002","unstructured":"Gero Dittmann and Andreas Herkersdorf . Network processor load balancing for high-speed links . In Proceedings of the 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems , 2002 . Gero Dittmann and Andreas Herkersdorf. Network processor load balancing for high-speed links. In Proceedings of the 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems, 2002."},{"key":"e_1_2_1_28_1","first-page":"124","volume-title":"ICT","author":"Kaushik Atul Kant","year":"2010","unstructured":"Atul Kant Kaushik , Emmanuel S. Pilli , and Ramesh C. Joshi . Network forensic analysis by correlation of attacks with network attributes . In ICT , pages 124 -- 128 , 2010 . Atul Kant Kaushik, Emmanuel S. Pilli, and Ramesh C. Joshi. Network forensic analysis by correlation of attacks with network attributes. In ICT, pages 124--128, 2010."},{"key":"e_1_2_1_29_1","first-page":"334","volume-title":"SIGCOMM","author":"Liu Zaoxing","year":"2019","unstructured":"Zaoxing Liu , Ran Ben-Basat , Gil Einziger , Yaron Kassner , Vladimir Braverman , Roy Friedman , and Vyas Sekar . Nitrosketch : robust and general sketch-based monitoring in software switches . In SIGCOMM , pages 334 -- 350 . ACM, 2019 . Zaoxing Liu, Ran Ben-Basat, Gil Einziger, Yaron Kassner, Vladimir Braverman, Roy Friedman, and Vyas Sekar. Nitrosketch: robust and general sketch-based monitoring in software switches. In SIGCOMM, pages 334--350. ACM, 2019."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3225058.3225078"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375457.1375472"},{"key":"e_1_2_1_33_1","first-page":"1249","volume-title":"IEEE\/ACM Trans. Netw.","author":"Chen Min","year":"2017","unstructured":"Min Chen , Shigang Chen , and Zhiping Cai . Counter tree : A scalable counter architecture for per-flow traffic measurement . IEEE\/ACM Trans. Netw. , pages 1249 -- 1262 , 2017 . Min Chen, Shigang Chen, and Zhiping Cai. Counter tree: A scalable counter architecture for per-flow traffic measurement. IEEE\/ACM Trans. Netw., pages 1249--1262, 2017."},{"key":"e_1_2_1_34_1","volume-title":"CoRR","author":"Yu Yun William","year":"2017","unstructured":"Yun William Yu and Griffin Weber . Hyperminhash : Jaccard index sketching in loglog space . CoRR , 2017 . Yun William Yu and Griffin Weber. Hyperminhash: Jaccard index sketching in loglog space. CoRR, 2017."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258193"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737531"},{"key":"e_1_2_1_37_1","first-page":"398","volume-title":"ICDT","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 ICDT , pages 398 -- 412 . Springer , 2005 . Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Efficient computation of frequent and top-k elements in data streams. In ICDT, pages 398--412. Springer, 2005."},{"key":"e_1_2_1_38_1","unstructured":"Related source code. https:\/\/github.com\/StingySketch\/Stingy-Sketch.  Related source code. https:\/\/github.com\/StingySketch\/Stingy-Sketch."},{"key":"e_1_2_1_39_1","volume-title":"https:\/\/github.com\/zhouyangpkuer\/Pyramid_Sketch_Framework","author":"Open","year":"2017","unstructured":"Open source code of augment and pyramid. https:\/\/github.com\/zhouyangpkuer\/Pyramid_Sketch_Framework , 2017 . Open source code of augment and pyramid. https:\/\/github.com\/zhouyangpkuer\/Pyramid_Sketch_Framework, 2017."},{"key":"e_1_2_1_40_1","unstructured":"Murmur hashing source code. https:\/\/github.com\/aappleby\/smhasher\/blob\/master\/src\/MurmurHash3.cpp.  Murmur hashing source code. https:\/\/github.com\/aappleby\/smhasher\/blob\/master\/src\/MurmurHash3.cpp."},{"key":"e_1_2_1_41_1","unstructured":"The web stream dataset. http:\/\/fimi.ua.ac.be\/data\/.  The web stream dataset. http:\/\/fimi.ua.ac.be\/data\/."},{"key":"e_1_2_1_42_1","unstructured":"The caida anonymized internet traces dataset. http:\/\/www.caida.org\/data\/overview\/.  The caida anonymized internet traces dataset. http:\/\/www.caida.org\/data\/overview\/."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948227"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2008.11.001"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948236"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.896150"},{"key":"e_1_2_1_50_1","first-page":"311","volume-title":"NSDI","author":"Li Yuliang","year":"2016","unstructured":"Yuliang Li , Rui Miao , Changhoon Kim , and Minlan Yu. Flowradar : A better netflow for data centers . In NSDI , pages 311 -- 324 . USENIX Association , 2016 . Yuliang Li, Rui Miao, Changhoon Kim, and Minlan Yu. Flowradar: A better netflow for data centers. In NSDI, pages 311--324. USENIX Association, 2016."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749443"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025112"},{"key":"e_1_2_1_53_1","volume-title":"Phillip B. Gibbons, and Avrim Blum. New streaming algorithms for fast detection of superspreaders","author":"Venkataraman Shobha","year":"2005","unstructured":"Shobha Venkataraman , Dawn Xiaodong Song , Phillip B. Gibbons, and Avrim Blum. New streaming algorithms for fast detection of superspreaders . In NDSS. The Internet Society , 2005 . Shobha Venkataraman, Dawn Xiaodong Song, Phillip B. Gibbons, and Avrim Blum. New streaming algorithms for fast detection of superspreaders. In NDSS. The Internet Society, 2005."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367508"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2933868"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230544"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3523210.3523220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:51:26Z","timestamp":1672224686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3523210.3523220"}},"subtitle":["a sketch framework for accurate and fast frequency estimation"],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":56,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.14778\/3523210.3523220"],"URL":"https:\/\/doi.org\/10.14778\/3523210.3523220","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}