The space complexity of approximating the frequency moments

The frequency moments of a sequence containing mi elements of type i, 1 les s 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 giv en one by one and cannot be stored. Surprisingly, it turns out that the num bers F-0, F-1, and F-2 can be approximated in logarithmic space, whereas th e 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 Academi c Press.