{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:10Z","timestamp":1779174850694,"version":"3.51.4"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p>Sketches are a popular approximation technique for large datasets and high-velocity data streams. While custom FPGA-based hardware has shown admirable throughput at sketching, the state-of-the-art exploits data parallelism by fully replicating resources and constructing independent summaries for every parallel input value. We consider this approach pessimistic, as it guarantees constant processing rates by provisioning resources for the worst case.<\/jats:p>\n          <jats:p>\n            We propose a novel optimistic sketching architecture for FPGAs that partitions a single sketch into multiple independent banks shared among all input values, thus significantly reducing resource consumption. However, skewed input data distributions can result in conflicting accesses to banks and impair the processing rate. To mitigate the effect of skew, we add mergers that exploit temporal locality by combining recent updates. Our evaluation shows that an optimistic architecture is feasible and reduces the utilization of critical FPGA resources proportionally to the number of parallel input values. We further show that FPGA accelerators provide up to 2.6\n            <jats:italic>x<\/jats:italic>\n            higher throughput than a recent CPU and GPU, while larger sketch sizes enabled by optimistic architectures improve accuracy by up to an order of magnitude in a realistic sketching application.\n          <\/jats:p>","DOI":"10.14778\/3579075.3579085","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T17:10:26Z","timestamp":1678122626000},"page":"1113-1125","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Optimistic Data Parallelism for FPGA-Accelerated Sketching"],"prefix":"10.14778","volume":"16","author":[{"given":"Martin","family":"Kiefer","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilias","family":"Poulakis","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eleni Tzirita","family":"Zacharatou","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volker","family":"Markl","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, DFKI GmbH, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.844498"},{"key":"e_1_2_1_3_1","volume-title":"Anonymized Internet Traces","author":"CAIDA.","year":"2019","unstructured":"CAIDA. 2019. Anonymized Internet Traces 2019 . https:\/\/catalog.caida.org\/details\/dataset\/passive_2019_pcap. Accessed: 2022-2-28. CAIDA. 2019. Anonymized Internet Traces 2019. https:\/\/catalog.caida.org\/details\/dataset\/passive_2019_pcap. Accessed: 2022-2-28."},{"key":"e_1_2_1_4_1","unstructured":"Ufuk Celebi. 2015. How Apache Flink handles backpressure. https:\/\/www.ververica.com\/blog\/how-flink-handles-backpressure.  Ufuk Celebi. 2015. How Apache Flink handles backpressure. https:\/\/www.ververica.com\/blog\/how-flink-handles-backpressure."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476287"},{"key":"e_1_2_1_6_1","volume-title":"29th International Conference on Field Programmable Logic and Applications. 278--285","author":"Chrysos G.","unstructured":"G. Chrysos , O. Papapetrou , D. Pnevmatikatos , A. Dollas , and M. Garofalakis . 2019. Data Stream Statistics Over Sliding Windows: How to Summarize 150 Million Updates Per Second on a Single Node . In 29th International Conference on Field Programmable Logic and Applications. 278--285 . G. Chrysos, O. Papapetrou, D. Pnevmatikatos, A. Dollas, and M. Garofalakis. 2019. Data Stream Statistics Over Sliding Windows: How to Summarize 150 Million Updates Per Second on a Single Node. In 29th International Conference on Field Programmable Logic and Applications. 278--285."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872787"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, 13--24","author":"Cormode Graham","year":"2005","unstructured":"Graham Cormode and Minos Garofalakis . 2005 . Sketching streams through the net: Distributed approximate query tracking . In Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, 13--24 . Graham Cormode and Minos Garofalakis. 2005. Sketching streams through the net: Distributed approximate query tracking. In Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, 13--24."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Graham Cormode Minos Garofalakis Peter J Haas Chris Jermaine etal 2011. Synopses for massive data: Samples histograms wavelets sketches. Foundations and Trends\u00ae in Databases 4 1-3 (2011) 1--294.  Graham Cormode Minos Garofalakis Peter J Haas Chris Jermaine et al. 2011. Synopses for massive data: Samples histograms wavelets sketches. Foundations and Trends \u00ae in Databases 4 1-3 (2011) 1--294.","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"key":"e_1_2_1_12_1","volume-title":"FPGA-accelerated analytics. now","author":"Istvan Zsolt","unstructured":"Zsolt Istvan , Kaan Kara , and David Sidler . 2020. FPGA-accelerated analytics. now , Hanover, MD . Zsolt Istvan, Kaan Kara, and David Sidler. 2020. FPGA-accelerated analytics. now, Hanover, MD."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430919"},{"key":"e_1_2_1_14_1","volume-title":"HyperLogLog Sketch Acceleration on FPGA. In 2020 30th International Conference on Field-Programmable Logic and Applications (FPL). 47--56","author":"Kulkarni Amit","year":"2020","unstructured":"Amit Kulkarni , Monica Chiosa , Thomas B. Preu\u00dfer , Kaan Kara , David Sidler , and Gustavo Alonso . 2020 . HyperLogLog Sketch Acceleration on FPGA. In 2020 30th International Conference on Field-Programmable Logic and Applications (FPL). 47--56 . Amit Kulkarni, Monica Chiosa, Thomas B. Preu\u00dfer, Kaan Kara, David Sidler, and Gustavo Alonso. 2020. HyperLogLog Sketch Acceleration on FPGA. In 2020 30th International Conference on Field-Programmable Logic and Applications (FPL). 47--56."},{"key":"e_1_2_1_15_1","unstructured":"Ping Li Anshumali Shrivastava Joshua L Moore and Arnd C K\u00f6nig. 2011. Hashing algorithms for large-scale learning. In Advances in neural information processing systems. 2672--2680.  Ping Li Anshumali Shrivastava Joshua L Moore and Arnd C K\u00f6nig. 2011. Hashing algorithms for large-scale learning. In Advances in neural information processing systems. 2672--2680."},{"key":"e_1_2_1_16_1","volume-title":"Data Streams. now","author":"Muthukrishnan S","unstructured":"S Muthukrishnan . 2005. Data Streams. now , Hanover, MD . S Muthukrishnan. 2005. Data Streams. now, Hanover, MD."},{"key":"e_1_2_1_17_1","volume-title":"2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE, 219--224","author":"Sateesan Arish","year":"2021","unstructured":"Arish Sateesan , Jo Vliegen , Simon Scherrer , Hsu-Chun Hsiao , Adrian Perrig , and Nele Mentens . 2021 . Speed records in network flow measurement on FPGA . In 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE, 219--224 . Arish Sateesan, Jo Vliegen, Simon Scherrer, Hsu-Chun Hsiao, Adrian Perrig, and Nele Mentens. 2021. Speed records in network flow measurement on FPGA. In 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE, 219--224."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of ACM\/USENIX Internet Measurement Conference'04","author":"Schweller Robert","year":"2004","unstructured":"Robert Schweller , Yan Chen , Elliot Parsons , Ashish Gupta , Gokhan Memik , and Yin Zhang . 2004 . Reverse hashing for sketch-based change detection on high-speed networks . In Proceedings of ACM\/USENIX Internet Measurement Conference'04 . Robert Schweller, Yan Chen, Elliot Parsons, Ashish Gupta, Gokhan Memik, and Yin Zhang. 2004. Reverse hashing for sketch-based change detection on high-speed networks. In Proceedings of ACM\/USENIX Internet Measurement Conference'04."},{"key":"e_1_2_1_19_1","volume-title":"FPMR: MapReduce Framework on FPGA (FPGA '10)","author":"Shan Yi","year":"2010","unstructured":"Yi Shan , Bo Wang , Jing Yan , Yu Wang , Ningyi Xu , and Huazhong Yang . 2010 . FPMR: MapReduce Framework on FPGA (FPGA '10) . Association for Computing Machinery , New York, NY, USA , 93--102. Yi Shan, Bo Wang, Jing Yan, Yu Wang, Ningyi Xu, and Huazhong Yang. 2010. FPMR: MapReduce Framework on FPGA (FPGA '10). Association for Computing Machinery, New York, NY, USA, 93--102."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3088500"},{"key":"e_1_2_1_21_1","volume-title":"2020 23rd Euromicro Conference on Digital System Design (DSD). 141--148","author":"Soto Javier E.","year":"2020","unstructured":"Javier E. Soto , Paulo Ubisse , Cecilia Hern\u00e1ndez , and Miguel Figueroa . 2020 . A hardware accelerator for entropy estimation using the top-k most frequent elements . In 2020 23rd Euromicro Conference on Digital System Design (DSD). 141--148 . Javier E. Soto, Paulo Ubisse, Cecilia Hern\u00e1ndez, and Miguel Figueroa. 2020. A hardware accelerator for entropy estimation using the top-k most frequent elements. In 2020 23rd Euromicro Conference on Digital System Design (DSD). 141--148."},{"key":"e_1_2_1_22_1","unstructured":"NYC Taxi and Limousine Commission. 2009-2016. TLC Trip Record Data. https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page.  NYC Taxi and Limousine Commission. 2009-2016. TLC Trip Record Data. https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page."},{"key":"e_1_2_1_23_1","volume-title":"International Conference on ReConFigurable Computing and FPGAs, ReConFig 2015","author":"Tong Da","year":"2015","unstructured":"Da Tong and Viktor K. Prasanna . 2015. High throughput sketch based online heavy change detection on FPGA . In International Conference on ReConFigurable Computing and FPGAs, ReConFig 2015 , Riviera Maya, Mexico , December 7-9, 2015 . 1--8. Da Tong and Viktor K. Prasanna. 2015. High throughput sketch based online heavy change detection on FPGA. In International Conference on ReConFigurable Computing and FPGAs, ReConFig 2015, Riviera Maya, Mexico, December 7-9, 2015. 1--8."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/TPDS.2017.2766633","article-title":"Sketch Acceleration on FPGA and its Applications in Network Anomaly Detection","volume":"29","author":"Tong D.","year":"2018","unstructured":"D. Tong and V. K. Prasanna . 2018 . Sketch Acceleration on FPGA and its Applications in Network Anomaly Detection . IEEE Transactions on Parallel and Distributed Systems 29 , 4 (April 2018), 929--942. D. Tong and V. K. Prasanna. 2018. Sketch Acceleration on FPGA and its Applications in Network Anomaly Detection. IEEE Transactions on Parallel and Distributed Systems 29, 4 (April 2018), 929--942.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2537805"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230544"},{"key":"e_1_2_1_28_1","volume-title":"2008 16th International Symposium on Field-Programmable Custom Computing Machines. 149--159","author":"Yeung Jackson H.C.","unstructured":"Jackson H.C. Yeung , C.C. Tsang , K.H. Tsoi , Bill S.H. Kwan , Chris C.C. Cheung , Anthony P.C. Chan , and Philip H.W. Leong . 2008. Map-reduce as a Programming Model for Custom Computing Machines . In 2008 16th International Symposium on Field-Programmable Custom Computing Machines. 149--159 . Jackson H.C. Yeung, C.C. Tsang, K.H. Tsoi, Bill S.H. Kwan, Chris C.C. Cheung, Anthony P.C. Chan, and Philip H.W. Leong. 2008. Map-reduce as a Programming Model for Custom Computing Machines. In 2008 16th International Symposium on Field-Programmable Custom Computing Machines. 149--159."},{"key":"e_1_2_1_29_1","volume-title":"2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig). 1--6.","author":"Zazo Jose Fernando","year":"2017","unstructured":"Jose Fernando Zazo , Sergio Lopez-Buedo , Mario Ruiz , and Gustavo Sutter . 2017 . A single-FPGA architecture for detecting heavy hitters in 100 Gbit\/s ethernet links . In 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig). 1--6. Jose Fernando Zazo, Sergio Lopez-Buedo, Mario Ruiz, and Gustavo Sutter. 2017. A single-FPGA architecture for detecting heavy hitters in 100 Gbit\/s ethernet links. In 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig). 1--6."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994534"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3579075.3579085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T17:13:54Z","timestamp":1678122834000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3579075.3579085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.14778\/3579075.3579085"],"URL":"https:\/\/doi.org\/10.14778\/3579075.3579085","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"2023-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}