# Separations for Estimating Large Frequency Moments on Data Streams

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2021.

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

- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)

## Abstract (arXiv)

We study the classical problem of moment estimation of an underlying vector whose n coordinates are implicitly defined through a series of updates in a data stream. We show that if the updates to the vector arrive in the random-order insertion-only model, then there exist space efficient algorithms with improved dependencies on the approximation parameter varepsilon. In particular, for any real p > 2, we first obtain an algorithm for Fp moment estimation using tildeOleft(frac1varepsilon4/p· n1-2/pright) bits of memory. Our techniques also give algorithms for Fp moment estimation with p>2 on arbitrary order insertion-only and turnstile streams, using tildeOleft(frac1varepsilon4/p· n1-2/pright) bits of space and two passes, which is the first optimal multi-pass Fp estimation algorithm up to log n factors. Finally, we give an improved lower bound of Omegaleft(frac1varepsilon2· n1-2/pright) for one-pass insertion-only streams. Our results separate the complexity of this problem both between random and non-random orders, as well as one-pass and multi-pass streams.