An improved data stream algorithm for frequency moments
Don Coppersmith, Ravi Kumar · 2004
We present a simple, one-pass, O(√n)-space data stream algorithm for approximating the third frequency moment. This is the first improvement to the O(n2/3)-space data stream algorithm of Alon, Matias, and Szegedy [AMS99]. the current known lower bound for this problem is Ω(n1/3) [BJKS02a].Our algorithm can also be generalized to an O(n1-1/(k-1))-space data stream algorithm for approximating the k-th frequency moment. Besides improving the O(n1--1/k)-space upper bound [AMS99], our algorithm beats the Ω(n1--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.