# Perfect Lp Sampling in a Data Stream

arXiv: https://arxiv.org/abs/1808.05497 · HTML: https://mlsanity.com/paper/1808.05497/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2018.

## Built on by (most cited first, 4 of 4)

- [One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space](https://mlsanity.com/paper/2311.14652/) (2023)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Adaptive Sketches for Robust Regression with Importance Sampling](https://mlsanity.com/paper/2207.07822/) (2022)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)

## Abstract (arXiv)

In this paper, we resolve the one-pass space complexity of Lp sampling for p ∈ (0,2). Given a stream of updates (insertions and deletions) to the coordinates of an underlying vector f ∈ ℝn, a perfect Lp sampler must output an index i with probability |fi|p/|f|pp, and is allowed to fail with some probability δ. So far, for p > 0 no algorithm has been shown to solve the problem exactly using poly( log n)-bits of space. In 2010, Monemizadeh and Woodruff introduced an approximate Lp sampler, which outputs i with probability (1 ± nu)|fi|p /|f|pp, using space polynomial in nu-1 and log(n). The space complexity was later reduced by Jowhari, Sauglam, and Tardos to roughly O(nu-p log2 n log δ-1) for p ∈ (0,2), which tightly matches the Omega(log2 n log δ-1) lower bound in terms of n and δ, but is loose in terms of nu. Given these nearly tight bounds, it is perhaps surprising that no lower bound exists in terms of nu---not even a bound of Omega(nu-1) is known. In this paper, we explain this phenomenon by demonstrating the existence of an O(log2 n log δ-1)-bit perfect Lp sampler for p ∈ (0,2). This shows that nu need not factor into the space of an Lp sampler, which closes the complexity of the problem for this range of p. For p=2, our bound is O(log3 n log δ-1)-bits, which matches the prior best known upper bound in terms of n,δ, but has no dependence on nu. For p<2, our bound holds in the random oracle model, matching the lower bounds in that model. Moreover, we show that our algorithm can be derandomized with only a O((log log n)2) blow-up in the space (and no blow-up for p=2). Our derandomization technique is general, and can be used to derandomize a large class of linear sketches.