The space complexity of approximating the frequency moments | Zendy

Noga Alon | Zendy; Yossi Matias | Zendy; Márió Szegedy | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The space complexity of approximating the frequency moments

Author(s) -

Noga Alon,

Yossi Matias,

Márió Szegedy

Publication year - 1996

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/237814.237823

Subject(s) - sequence (biology) , logarithm , space (punctuation) , mathematics , computational complexity theory , combinatorics , discrete mathematics , algorithm , computer science , mathematical analysis , operating system , genetics , biology

The frequency moments of a sequence containing mi elements of type i, for 1 i n, are the numbers Fk = P n=1 m k . 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;F1 and F2 can be approximated in logarithmic space, whereas the approximation of Fk for k 6 requires n (1) space. Applications to data bases are mentioned as well.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research