Unbiased Insights: Optimal Streaming Algorithms for ${\ell }_p$ Sampling, the Forget Model, and Beyond

Abstract

We study ${\ell }_p$ sampling and frequency moment estimation in a single-pass insertion-only data stream. For $p\in (0,2)$, we present a nearly space-optimal approximate ${\ell }_p$ sampler that uses $\tilde{O}(\log n\log (1/\hat{I}´))$ bits of space and for $p=2$, we present a sampler with space complexity $\tilde{O}({\log }^{2}n\log (1/\hat{I}´))$. This space complexity is optimal for $p\in (0,2)$ and improves upon prior work by a $\log n$ factor. We further extend our construction to a continuous ${\ell }_p$ sampler, which outputs a valid sample index at every point during the stream. Leveraging these samplers, we design nearly unbiased estimators for $F_p$ in data streams that include forget operations, which reset individual element frequencies and introduce significant non-linear challenges. As a result, we obtain near-optimal algorithms for estimating $F_p$ for all $p$ in this model, originally proposed by Pavan, Chakraborty, Vinodchandran, and Meel [PODS'24], resolving all three open problems they posed. Furthermore, we generalize this model to what we call the suffix-prefix deletion model, and extend our techniques to estimate entropy as a corollary of our moment estimation algorithms. Finally, we show how to handle arbitrary coordinate-wise functions during the stream, for any $g\in \mathbb{G}$, where $\mathbb{G}$ includes all (linear or non-linear) contraction functions.

To appear in PODS 2026