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,414 | Single Update Sketch with Variable Counter Structure | 2023 | VLDB | 5.4304732e-05 |
| 10,813 | RGS-Sketch: An Accurate, Invertible, and Mergeable Sketch for Online Super Spreader Detection in High-speed Data Streams | 2025 | VLDB | 5.093636e-05 |
| 11,196 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 5.093636e-05 |
| 11,263 | Enhancing Accuracy for Super Spreader Identification in High-Speed Data Streams | 2024 | VLDB | 5.093636e-05 |
| 11,503 | Bayesian Sketches for Volume Estimation in Data Streams | 2023 | VLDB | 5.093636e-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 |
|---|---|---|---|---|
| 51 | Dremel: Interactive Analysis of Web-Scale Datasets | 2010 | VLDB | 0.0004291425 |
| 689 | On Synopses for Distinct-Value Estimation Under Multiset Operations | 2007 | SIGMOD | 0.00014940023 |
| 1,225 | Processing a Trillion Cells per Mouse Click | 2012 | VLDB | 0.00011590013 |
| 1,294 | Augmented Sketch: Faster and More Accurate Stream Processing | 2016 | SIGMOD | 0.00011291308 |
| 1,905 | Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing | 2018 | SIGMOD | 9.5034849e-05 |
| 2,013 | Space Efficient Mining of Multigraph Streams | 2005 | PODS | 9.3068345e-05 |
| 2,549 | Web Caching for Database Applications with Oracle Web Cache | 2002 | SIGMOD | 8.4300694e-05 |
| 5,873 | QRelX: Generating Meaningful Queries that Provide Cardinality Assurance | 2010 | SIGMOD | 6.0596577e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,193 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD |
| 2 | 12,724 | Join-Distinct Aggregate Estimation over Update Streams | 2005 | PODS |
| 3 | 11,196 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD |
| 4 | 2,697 | Sketching Probabilistic Data Streams | 2007 | SIGMOD |
| 5 | 12,034 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD |
| 6 | 1,045 | Sketching Streams Through the Net: Distributed Approximate Query Tracking | 2005 | VLDB |
| 7 | 4,472 | Relative Error Streaming Quantiles | 2021 | PODS |
| 8 | 817 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD |
| 9 | 12,305 | Space-Efficient Estimation of Statistics over Sub-Sampled Streams | 2012 | PODS |
| 10 | 11,263 | Enhancing Accuracy for Super Spreader Identification in High-Speed Data Streams | 2024 | VLDB |