The Space Complexity of Approximating the Frequency Moments

Authors: Noga Alon, Yossi Matias, Mario Szegedy - ACM Symposium on Theory of Computing, STOC 1996 cited by 1,177

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