Randomized Error Removal for Online Spread Estimation in Data Streaming
Summary: Introduces multi-flow spread sketches using randomized error removal to improve per-flow distinct counting under tight memory. Formal analysis and hardware/software evaluations show superior accuracy, update throughput, and online query throughput over prior art. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Haibo Wang (University of Florida)
- 2. Chaoyi Ma (University of Florida)
- 3. Olufemi O Odegbile (University of Florida)
- 4. Shigang Chen (University of Florida)
- 5. Jih-Kwon Peir (University of Florida)
BibTeX Citation
@article{wang_vldb21,
title = {{Randomized Error Removal for Online Spread Estimation in Data Streaming}},
author = {Wang, Haibo and Ma, Chaoyi and Odegbile, Olufemi O and Chen, Shigang and Peir, Jih-Kwon},
journal = {PVLDB},
series = {{VLDB} '21},
volume = {14},
number = {6},
pages = {1040--1052},
doi = {10.14778/3447689.3447707},
url = {https://doi.org/10.14778/3447689.3447707},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,585 | Single Update Sketch with Variable Counter Structure | 2023 | VLDB | 5.3086279e-05 |
| 11,222 | RGS-Sketch: An Accurate, Invertible, and Mergeable Sketch for Online Super Spreader Detection in High-speed Data Streams | 2025 | VLDB | 4.9793485e-05 |
| 11,538 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 4.9793485e-05 |
| 11,591 | Enhancing Accuracy for Super Spreader Identification in High-Speed Data Streams | 2024 | VLDB | 4.9793485e-05 |
| 11,812 | Bayesian Sketches for Volume Estimation in Data Streams | 2023 | VLDB | 4.9793485e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 49 | Dremel: Interactive Analysis of Web-Scale Datasets | 2010 | VLDB | 0.00043160717 |
| 707 | On Synopses for Distinct-Value Estimation Under Multiset Operations | 2007 | SIGMOD | 0.00014640173 |
| 1,210 | Processing a Trillion Cells per Mouse Click | 2012 | VLDB | 0.00011527605 |
| 1,319 | Augmented Sketch: Faster and More Accurate Stream Processing | 2016 | SIGMOD | 0.00011045888 |
| 1,970 | Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing | 2018 | SIGMOD | 9.2902522e-05 |
| 2,054 | Space Efficient Mining of Multigraph Streams | 2005 | PODS | 9.1135465e-05 |
| 2,593 | Web Caching for Database Applications with Oracle Web Cache | 2002 | SIGMOD | 8.243812e-05 |
| 5,972 | QRelX: Generating Meaningful Queries that Provide Cardinality Assurance | 2010 | SIGMOD | 5.9311519e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,318 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD |
| 2 | 13,014 | Join-Distinct Aggregate Estimation over Update Streams | 2005 | PODS |
| 3 | 11,538 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD |
| 4 | 2,738 | Sketching Probabilistic Data Streams | 2007 | SIGMOD |
| 5 | 12,329 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD |
| 6 | 1,066 | Sketching Streams Through the Net: Distributed Approximate Query Tracking | 2005 | VLDB |
| 7 | 4,564 | Relative Error Streaming Quantiles | 2021 | PODS |
| 8 | 842 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD |
| 9 | 12,596 | Space-Efficient Estimation of Statistics over Sub-Sampled Streams | 2012 | PODS |
| 10 | 11,591 | Enhancing Accuracy for Super Spreader Identification in High-Speed Data Streams | 2024 | VLDB |