Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes

Naomi Green-Maimon, Or Zamir

Estimating the second frequency moment $F_2$ of a data stream up to a $(1\pm \epsilon )$ factor is a central problem in the streaming literature. For errors $\varepsilon > Ω(1/\…