[PDF][PDF] The space complexity of approximating the frequency moments
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996•dl.acm.org
The frequency moments of a sequence containing m~ elements of type i, for 1~ z~ n, are the
numbers F&=~~= 1 m?. 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 FO, F1 and F2 can be
approximated in logarithmic space, whereas the approximation of F& for k~ 6 requires nQ (l)
space. Applications to data bases are mentioned as well.
numbers F&=~~= 1 m?. 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 FO, F1 and F2 can be
approximated in logarithmic space, whereas the approximation of F& for k~ 6 requires nQ (l)
space. Applications to data bases are mentioned as well.
Abstract
The frequency moments of a sequence containing m~ elements of type i, for 1~ z~ n, are the numbers F&=~~= 1 m?. 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 FO, F1 and F2 can be approximated in logarithmic space, whereas the approximation of F& for k~ 6 requires nQ (l) space. Applications to data bases are mentioned as well.