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

CREATORHonghao Lin, Hoai-An Nguyen, William Swartworth, David P. Woodruff
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-07067

Browse the full library · About the Tower of Babel