Unbiased Insights: Optimal Streaming Algorithms for ℓ p \ell_{p} Sampling, the Forget Model, and Beyond
Honghao Lin, Hoai-An Nguyen, William Swartworth, David P. Woodruff · 2025
Read Unbiased Insights: Optimal Streaming Algorithms for ℓ p \ell_{p} Sampling, the Forget Model, and Beyond by Honghao Lin, Hoai-An Nguyen, William Swartworth, David P. Woodruff (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-07067.txt.
Description
Honghao Lin and three co-authors design sampling tools for huge data streams in this two thousand twenty-five paper. A stream passes once, too fast to store, so algorithms must sketch it on the fly. One key task is drawing a random item with chance tied to its frequency raised to a power. The authors give samplers that use nearly the least possible memory. One version updates its sample at every moment of the stream.
They then tackle streams where items can be forgotten, resetting their counts. That twist breaks older estimators with heavy bias. Their near-unbiased estimators cover the full range of powers in this harder model. The results serve the theory of data streams and the systems built on it.
Catalog record
| CREATOR | Honghao Lin, Hoai-An Nguyen, William Swartworth, David P. Woodruff |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 149 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-07067