The space complexity of approximating the frequency moments

The frequency moments of a sequence containing mi elements of type i, 1 less than or equal to i less than or equal to n, are the numbers F-k = Sigma(i=1)(n), m(i)(k). We consider the space complexity of randomized algorithms that approximate the numbers F-k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F-0, F-1, and F-2 can be approximated in logarithmic space, whereas the approximation of F-k for k greater than or equal to 6 requires n(Omega(1)) space. Applications to data bases are mentioned as well. (C) 1999 Academic Press.