TY - GEN

T1 - The space complexity of approximating the frequency moments

AU - Alon, Noga

AU - Matias, Yossi

AU - Szegedy, Mario

N1 - Funding Information:
*AT&T Bell Labs, Murray Hill, NJ 07974, USA and Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. Email: noga@math.tau.ac. il. Research supported in part by a USA-Israel BSF grant and the Fund for Basic Research administered by the Israel Academy Sciences. t AT&T Bell Labs, matiasQresearch .att. corn. t AT&T Labs, ms@research. corn.

PY - 1996/7/1

Y1 - 1996/7/1

N2 - The frequency moments of a sequence containing mi elements of type i, for 1 ≤ i ≤ n, are the numbers Fk = Σn i=1 mki. 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, for 1 ≤ i ≤ n, are the numbers Fk = Σn i=1 mki. 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 - http://www.scopus.com/inward/record.url?scp=0029719644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029719644&partnerID=8YFLogxK

U2 - 10.1145/237814.237823

DO - 10.1145/237814.237823

M3 - Conference contribution

AN - SCOPUS:0029719644

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 20

EP - 29

BT - Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996

PB - Association for Computing Machinery

T2 - 28th Annual ACM Symposium on Theory of Computing, STOC 1996

Y2 - 22 May 1996 through 24 May 1996

ER -