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

CREATORHonghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE242 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22816

Browse the full library · About the Tower of Babel