{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T18:18:53Z","timestamp":1782929933976,"version":"3.54.5"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p>Measuring flow spread in real time from large, high-rate data streams has numerous practical applications, where a data stream is modeled as a sequence of data items from different flows and the spread of a flow is the number of distinct items in the flow. Past decades have witnessed tremendous performance improvement for single-flow spread estimation. However, when dealing with numerous flows in a data stream, it remains a significant challenge to measure per-flow spread accurately while reducing memory footprint. The goal of this paper is to introduce new multi-flow spread estimation designs that incur much smaller processing overhead and query overhead than the state of the art, yet achieves significant accuracy improvement in spread estimation. We formally analyze the performance of these new designs. We implement them in both hardware and software, and use real-world data traces to evaluate their performance in comparison with the state of the art. The experimental results show that our best sketch significantly improves over the best existing work in terms of estimation accuracy, data item processing throughput, and online query throughput.<\/jats:p>","DOI":"10.14778\/3447689.3447707","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:20:06Z","timestamp":1618244406000},"page":"1040-1052","source":"Crossref","is-referenced-by-count":43,"title":["Randomized error removal for online spread estimation in data streaming"],"prefix":"10.14778","volume":"14","author":[{"given":"Haibo","family":"Wang","sequence":"first","affiliation":[{"name":"University of Florida"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chaoyi","family":"Ma","sequence":"additional","affiliation":[{"name":"University of Florida"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olufemi O","family":"Odegbile","sequence":"additional","affiliation":[{"name":"University of Florida"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shigang","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Florida"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jih-Kwon","family":"Peir","sequence":"additional","affiliation":[{"name":"University of Florida"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2016. Retailrocket Recommender System Dataset. https:\/\/www.kaggle.com\/retailrocket\/ecommerce-dataset.  2016. Retailrocket Recommender System Dataset. https:\/\/www.kaggle.com\/retailrocket\/ecommerce-dataset."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Twenty-Second ACM SIGMOD\/PODS Workshop on Management and Processing of Data Streams. 1--3.","author":"Akella A."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564762"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_5_1","volume-title":"Estimation of Topic Cardinality in Document Collections. In SIAM Conference on Data Mining (SDM 10)","author":"Bronselaer A."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/977400.977961"},{"key":"e_1_2_1_7_1","volume-title":"Estimating Dominance Norms of Multiple Data Streams. In European Symposium on Algorithms. Springer, 148--160","author":"Cormode G."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065201"},{"key":"e_1_2_1_9_1","volume-title":"Loglog Counting of Large Cardinalities. In European Symposium on Algorithms. Springer, 605--617","author":"Durand M."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2671225.2671230"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2006.882836"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"P. Flajolet \u00c9. Fusy O. Gandouet and F. Meunier. 2007. Hyperloglog: the Analysis of a Near-optimal Cardinality Estimation Algorithm. In Discrete Mathematics and Theoretical Computer Science. Discrete Mathematics and Theoretical Computer Science 137--156.  P. Flajolet \u00c9. Fusy O. Gandouet and F. Meunier. 2007. Hyperloglog: the Analysis of a Near-optimal Cardinality Estimation Algorithm. In Discrete Mathematics and Theoretical Computer Science. Discrete Mathematics and Theoretical Computer Science 137--156.","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2007.142"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350259"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098831"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2930611.2930632"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833701"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2015.2423675"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342076"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934906"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920886"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/997150.997156"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716281.2836099"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1155\/2005\/962135"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882948"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/637201.637222"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1251254.1251258"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2010.032210.00054"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"L. Tang Q. Huang and P. Lee. 2020. SpreadSketch: Toward Invertible and Network-Wide Detection of Superspreaders. (2020).  L. Tang Q. Huang and P. Lee. 2020. SpreadSketch: Toward Invertible and Network-Wide Detection of Superspreaders. (2020).","DOI":"10.1109\/INFOCOM41043.2020.9155541"},{"key":"e_1_2_1_32_1","unstructured":"UCSD. 2015. CAIDA UCSD Anonymized 2015 Internet Traces on Jan. 17. https:\/\/www.caida.org\/data\/passive\/passive_2015_dataset.xml.  UCSD. 2015. CAIDA UCSD Anonymized 2015 Internet Traces on Jan. 17. https:\/\/www.caida.org\/data\/passive\/passive_2015_dataset.xml."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807323"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447707"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.2991007"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-018-0583-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78925"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745870"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230544"},{"key":"e_1_2_1_41_1","volume-title":"IEEE INFOCOM","author":"Yoon M.","year":"2009"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482631"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2877700"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3143314.3078593"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183726"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366699"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3447689.3447707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:21:06Z","timestamp":1672226466000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3447689.3447707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.14778\/3447689.3447707"],"URL":"https:\/\/doi.org\/10.14778\/3447689.3447707","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2]]}}}