optimal approximations of the frequency moments of data streams
We give a 1-pass  ( m 1-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  ( m 1-2?p ) space algorithm for the L p difference problem for any p > 2. This essentially matches the known ?( m 1-2? p - o (1) ) lower bound of [12, 2]. Finally the update time of our algorithms is  (1).
optimality frequency moments data streaming space algorithm computation lower bound update timing streaming algorithms