The space complexity of approximating the frequency moments

Noga Alon, Yossi Matias, Mario Szegedy

Research output: Contribution to journalArticle

592 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)137-147
Number of pages11
JournalJournal of Computer and System Sciences
Volume58
Issue number1
DOIs
StatePublished - Feb 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'The space complexity of approximating the frequency moments'. Together they form a unique fingerprint.

  • Cite this