an improved data stream algorithm for frequency moments
We present a simple, one-pass,  (? n )-space data stream algorithm for approximating the third frequency moment. This is the first improvement to the  ( n 2/3 )-space data stream algorithm of Alon, Matias, and Szegedy [AMS99]. the current known lower bound for this problem is ?( n 1/3 ) [BJKS02a].Our algorithm can also be generalized to an  ( n 1-1/( k -1) )-space data stream algorithm for approximating the k -th frequency moment. Besides improving the  ( n 1--1/ k )-space upper bound [AMS99], our algorithm beats the ?( n 1--1/ k )-sampling lower bound [BKS01] for this problem.Our method suggests a unified perspective of space-efficient data stream algorithms for all frequency moments.
data streaming algorithm approximation lower bound general method efficiency sampling space