An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits

摘要: In this paper, we provide the first optimal algorithm for remaining open question from seminal paper of Alon, Matias, and Szegedy: approximating large frequency moments. We give an upper bound on space required to find a k-th moment O(n^(1-2/k)) bits that matches, up constant factor, lower Woodruff et. al epsilon k. Our makes single pass over stream works any k > 3. It is based upon two major technical accomplishments: first, finding heavy elements in stream; second, technique using Martingale Sketches which gives reduction problem all problem. also polylogarithmic improvement moments, functions, spatial data streams, measuring independence sets.