{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:55:19Z","timestamp":1773482119248,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>\n            Data analysts often need to characterize a data stream as a first step to its further processing. Some of the initial insights to be gained include, e.g., the cardinality of the data set and its frequency distribution. Such information is typically extracted by using\n            <jats:italic>sketch<\/jats:italic>\n            algorithms, now widely employed to process very large data sets in manageable space and in a single pass over the data. Often, analysts need more than one parameter to characterize the stream. However, computing multiple sketches becomes expensive even when using high-end CPUs. Exploiting the increasing adoption of hardware accelerators, this paper proposes\n            <jats:italic>SKT<\/jats:italic>\n            , an FPGA-based accelerator that can compute several sketches along with basic statistics (average, max, min, etc.) in a single pass over the data. SKT has been designed to characterize a data set by calculating its cardinality, its second frequency moment, and its frequency distribution. The design processes data streams coming either from PCIe or TCP\/IP, and it is built to fit emerging cloud service architectures, such as Microsoft's Catapult or Amazon's AQUA. The paper explores the trade-offs of designing sketch algorithms on a spatial architecture and how to combine several sketch algorithms into a single design. The empirical evaluation shows how SKT on an FPGA offers a significant performance gain over high-end, server-class CPUs.\n          <\/jats:p>","DOI":"10.14778\/3476249.3476287","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"2369-2382","source":"Crossref","is-referenced-by-count":18,"title":["SKT"],"prefix":"10.14778","volume":"14","author":[{"given":"Monica","family":"Chiosa","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}]},{"given":"Thomas B.","family":"Preu\u00dfer","sequence":"additional","affiliation":[{"name":"Accemic Technologies, Dresden, Germany"}]},{"given":"Gustavo","family":"Alonso","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303978"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_3_1","volume-title":"Retrieved","year":"2020","unstructured":"AWSCloud. 2020 . AQUA (Advanced Query Accelerator) for Amazon Redshift . Retrieved December 21, 2020 from https:\/\/pages.awscloud.com\/AQUA_Preview.html AWSCloud. 2020. AQUA (Advanced Query Accelerator) for Amazon Redshift. Retrieved December 21, 2020 from https:\/\/pages.awscloud.com\/AQUA_Preview.html"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380718.2380723"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056097"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2018.022071131"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3080008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083598"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.5"},{"key":"e_1_2_1_13_1","unstructured":"L.H. Crockett S.A. Elliot M.A. Enderwitz and R.W. Stewart. 2014. The Zynq Book (1. ed.). Strathclyde Academic Media UK.  L.H. Crockett S.A. Elliot M.A. Enderwitz and R.W. Stewart. 2014. The Zynq Book (1. ed.). Strathclyde Academic Media UK."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.420"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3361682"},{"key":"e_1_2_1_16_1","volume-title":"Retrieved","author":"DataSketches Apache","year":"2021","unstructured":"Apache DataSketches . 2021 . The Business Challenge: Analyzing Big Data Quickly . Retrieved January 20, 2021 from https:\/\/datasketches.apache.org\/docs\/Background\/TheChallenge.html Apache DataSketches. 2021. The Business Challenge: Analyzing Big Data Quickly. Retrieved January 20, 2021 from https:\/\/datasketches.apache.org\/docs\/Background\/TheChallenge.html"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/285243.285287"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3307441.3307446"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00012"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ARES.2015.101"},{"key":"e_1_2_1_22_1","volume-title":"Retrieved","author":"He Zhenhao","year":"2020","unstructured":"Zhenhao He . 2020 . Vitis with 100 Gbps TCP\/IP . Retrieved January 20, 2021 from https:\/\/github.com\/fpgasystems\/Vitis_with_100Gbps_TCP-IP Zhenhao He. 2020. Vitis with 100 Gbps TCP\/IP. Retrieved January 20, 2021 from https:\/\/github.com\/fpgasystems\/Vitis_with_100Gbps_TCP-IP"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.3929\/ethz-b-000487920"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3282307"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_1_26_1","volume-title":"Retrieved","author":"Hoffa Felipe","year":"2017","unstructured":"Felipe Hoffa . 2017 . Counting uniques faster in BigQuery with HyperLogLog++ . Retrieved December 21, 2020 from https:\/\/cloud.google.com\/blog\/products\/gcp\/counting-uniques-faster-in-bigquery-with-hyperloglog Felipe Hoffa. 2017. Counting uniques faster in BigQuery with HyperLogLog++. Retrieved December 21, 2020 from https:\/\/cloud.google.com\/blog\/products\/gcp\/counting-uniques-faster-in-bigquery-with-hyperloglog"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3007787.3001146"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994512"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2016.7577353"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035946"},{"key":"e_1_2_1_31_1","volume-title":"Parallel Programming for FPGAs. arXiv preprint arXiv:1805.03648","author":"Kastner Ryan","year":"2018","unstructured":"Ryan Kastner , Janarbek Matai , and Stephen Neuendorffer . 2018. Parallel Programming for FPGAs. arXiv preprint arXiv:1805.03648 ( 2018 ). Ryan Kastner, Janarbek Matai, and Stephen Neuendorffer. 2018. Parallel Programming for FPGAs. arXiv preprint arXiv:1805.03648 (2018)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3430915.3442428"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL50879.2020.00019"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132756"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2008.11.001"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353418"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"e_1_2_1_39_1","volume-title":"Retrieved","author":"Redshift Amazon","year":"2020","unstructured":"Amazon Redshift . [n.d.]. Using HyperLogLog sketches in Amazon Redshift . Retrieved December 21, 2020 from https:\/\/docs.aws.amazon.com\/redshift\/latest\/dg\/hyperloglog-overview.html Amazon Redshift. [n.d.]. Using HyperLogLog sketches in Amazon Redshift. Retrieved December 21, 2020 from https:\/\/docs.aws.amazon.com\/redshift\/latest\/dg\/hyperloglog-overview.html"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850585"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2015.56"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2019.00053"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247503"},{"key":"e_1_2_1_44_1","volume-title":"Retrieved","author":"Simeonov Sim","year":"2019","unstructured":"Sim Simeonov . 2019 . Advanced Analytics with HyperLogLog Functions in Apache Spark . Retrieved January 30, 2021 from https:\/\/databricks.com\/blog\/2019\/05\/08\/advanced-analytics-with-apache-spark.html Sim Simeonov. 2019. Advanced Analytics with HyperLogLog Functions in Apache Spark. Retrieved January 30, 2021 from https:\/\/databricks.com\/blog\/2019\/05\/08\/advanced-analytics-with-apache-spark.html"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830806"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2927964.2927977"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2766633"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3195638.3195676"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732967.2732972"},{"key":"e_1_2_1_50_1","volume-title":"Retrieved","year":"2020","unstructured":"Xilinx. [n.d.]. Xilinx Adaptive Compute Cluster (XACC) Program . Retrieved December 21, 2020 fromhttps:\/\/www.xilinx.com\/support\/university\/XUP-XACC.html Xilinx. [n.d.]. Xilinx Adaptive Compute Cluster (XACC) Program. Retrieved December 21, 2020 fromhttps:\/\/www.xilinx.com\/support\/university\/XUP-XACC.html"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2012.27"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028788.1028802"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559899"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:04:48Z","timestamp":1672221888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476287"}},"subtitle":["a one-pass multi-sketch data analytics accelerator"],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":53,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476287"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476287","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}