The space complexity of approximating the frequency moments

Abstract

The frequency moments of a sequence containing m i elements of type i, for 1 i n, are the numbers Fk = P n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the numbers Fk , when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0