An improved data stream algorithm for frequency moments

Abstract

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.