The space complexity of approximating the frequency moments

Noga Alon; Yossi Matias; Mario Szegedy

doi:10.1006/jcss.1997.1545

The space complexity of approximating the frequency moments

Noga Alon
, Yossi Matias
, Mario Szegedy

Research output: Contribution to journal › Article › peer-review

876 Scopus citations

Abstract

The frequency moments of a sequence containing m_i elements of type i, 1≤i≤n, are the numbers F_k=Σⁿ_i=1m^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 F₀, F₁, and F₂ can be approximated in logarithmic space, whereas the approximation of F_k for k≥6 requires n^Ω(1) space. Applications to data bases are mentioned as well.

Original language	English (US)
Pages (from-to)	137-147
Number of pages	11
Journal	Journal of Computer and System Sciences
Volume	58
Issue number	1
DOIs	https://doi.org/10.1006/jcss.1997.1545
State	Published - Feb 1999
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1006/jcss.1997.1545

Cite this

@article{939402db0e744065a0952ef01046642c,

title = "The space complexity of approximating the frequency moments",

abstract = "The frequency moments of a sequence containing mi elements of type i, 1≤i≤n, are the numbers Fk=Σni=1mki. 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.",

author = "Noga Alon and Yossi Matias and Mario Szegedy",

note = "Funding Information: - Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. Research supported in part by a USA-Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.",

year = "1999",

month = feb,

doi = "10.1006/jcss.1997.1545",

language = "English (US)",

volume = "58",

pages = "137--147",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - The space complexity of approximating the frequency moments

AU - Alon, Noga

AU - Matias, Yossi

AU - Szegedy, Mario

N1 - Funding Information: - Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. Research supported in part by a USA-Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.

PY - 1999/2

Y1 - 1999/2

N2 - The frequency moments of a sequence containing mi elements of type i, 1≤i≤n, are the numbers Fk=Σni=1mki. 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.

AB - The frequency moments of a sequence containing mi elements of type i, 1≤i≤n, are the numbers Fk=Σni=1mki. 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.

UR - https://www.scopus.com/pages/publications/0033077324

UR - https://www.scopus.com/pages/publications/0033077324#tab=citedBy

U2 - 10.1006/jcss.1997.1545

DO - 10.1006/jcss.1997.1545

M3 - Article

AN - SCOPUS:0033077324

SN - 0022-0000

VL - 58

SP - 137

EP - 147

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 1

ER -

The space complexity of approximating the frequency moments

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this