The Space Complexity of Approximating the Frequency Moments

摘要

The frequency moments of a sequence containingmielements of typei, 1⩽i⩽n, are the numbersFk=∑ni=1 mki. We consider the space complexity of randomized algorithms that approximate the numbersFk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF0,F1, andF2can be approximated in logarithmic space, whereas the approximation ofFkfork⩾6 requiresnΩ(1)space. Applications to data bases are mentioned as well.