A Lower Bound for Estimating High Moments of a Data Stream

Understand

We show an improved lower bound for the Fp estimation problem in a data stream setting for p>2.

• A data stream is a sequence of items from the domain [n] with possible repetitions.
• The frequency vector x is an n-dimensional non-negative integer vector x such that x(i) is the number of occurrences of i in the sequence.
• Given an accuracy parameter Omega(n^{-1/p}) < \epsilon < 1, the problem of estimating Fp is to estimate \norm{x}_p^p = \sum_{i \in [n]} \abs{x(i)}^p correctly to within a relative accuracy of 1\pm \epsilon with high constant probability in an online fashion and using as little space as possible.