L p L_{p} Sampling in Distributed Data Streams with Applications to Adversarial Robustness
Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou · 2025
Read L p L_{p} Sampling in Distributed Data Streams with Applications to Adversarial Robustness by Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, 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-2510-22816.txt.
Introduction
Many servers hold one data stream, yet sampling must stay global. Honghao Lin leads a team with four co-authors. In 2025 they solve perfect Lp sampling in that setting. Lp sampling picks an index with chance tied to frequency power. A central coordinator limits communication.
Their algorithm uses communication that is near optimal. Optimality holds up to log factors. They then build robust monitoring protocols. Those protocols estimate frequency moments. Adversaries can adapt inputs in their setting. Their method still gives tight approximations. Sampling is a core primitive for stream tasks. Such tasks include heavy hitter detection and sparse recovery.
Catalog record
| CREATOR | Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 242 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22816