General Terms

We give a 1-pass Õ(m1−2/k)-space algorithm for computing the k-th frequency moment of a data stream for any real k> 2. Together with the lower bounds of [1, 2, 4], this resolves the main problem left open by Alon et al in 1996 [1]. Our algorithm also works for streams with deletions and thus gives an Õ(m1−2/p) space algorithm for the Lp difference problem for any p> 2. This essentially matches the known Ω(m 1−2/p−o(1) ) lower bound of [13, 2]. Finally the update time of our algorithm is Õ(1)