Optimal Approximations of the Frequency Moments
| Data(s) |
08/10/2004
08/10/2004
02/07/2004
|
|---|---|
| Resumo |
We give a one-pass, O~(m^{1-2/k})-space algorithm for estimating the k-th frequency moment of a data stream for any real k>2. Together with known lower bounds, this resolves the main problem left open by Alon, Matias, Szegedy, STOC'96. Our algorithm enables deletions as well as insertions of stream elements. |
| Formato |
18 p. 3705201 bytes 761567 bytes application/postscript application/pdf |
| Identificador |
AIM-2004-014 |
| Idioma(s) |
en_US |
| Relação |
AIM-2004-014 |
| Palavras-Chave | #AI |
