Perfect L p L_{p} Sampling with Polylogarithmic Update Time
William Swartworth, David P. Woodruff, Samson Zhou · 2025
Read Perfect L p L_{p} Sampling with Polylogarithmic Update Time by William Swartworth, David P. Woodruff, Samson Zhou (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-2512-00632.txt.
Description
William Swartworth, David Woodruff, and Samson Zhou work on streaming algorithms, where data flows past and cannot all be stored. Their 2025 paper concerns perfect sampling from a stream under a measure called Lp sampling. A sampler should pick an index with chance tied to the size of its entry.
An earlier method from Jayaram and Woodruff set up this kind of sampling for changing streams. Updates can add to or subtract from entries as the stream runs. Swartworth and his coauthors push for much faster updates, with time that grows very slowly as the stream grows. Fast sampling helps systems watch huge data flows in real time.
Catalog record
| CREATOR | William Swartworth, David P. Woodruff, Samson Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 113 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00632