### Abstract

The frequency moments of a sequence containing m_{i} elements of type i, 1≤i≤n, are the numbers F_{k}=Σ^{n}_{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_{0}, F_{1}, and F_{2} 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 | |

State | Published - Feb 1999 |

Externally published | Yes |

### 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

Alon, N., Matias, Y., & Szegedy, M. (1999). The space complexity of approximating the frequency moments.

*Journal of Computer and System Sciences*,*58*(1), 137-147. https://doi.org/10.1006/jcss.1997.1545