The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containing m, elements of type i, for 1 - i - n, are the numbers F sub k = sum from n to i=1 m sup k sub i. We consider the space complexity of randomized algorithms that approximate the numbers F sub k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F sub 0, F sub 1 and F sub 2 can be approximated in logarithmic space, whereas the approximation of F sub k for k >- 6 requires n sup (OMEGA)(1)) space. Applications to data bases are mentioned as well.