Data streams emerged as a critical model for multiple applications that must handle vast amounts of data. One of the most influential papers in streaming is the celebrated and award-winning "AMS" paper on computing frequency moments by Alon, Matias and Szegedy [AMS99]. The main question left open (and explicitly asked) by AMS ten years ago is to give the precise characterization for which functions G on frequency vectors mi (1 ≤ i ≤ n) can ∑ i∈[n] G(mi) be approximated efficiently, where by "efficiently" we mean a single pass over data stream and polylogarithmic memory. No such characterization was known despite a tremendous amount of research on frequency-based functions in streaming literature. In this paper, we finally resolve the AMS main question and give a precise characterization (in fact a zero-one law) for all monotonically increasing functions on frequencies that are zero at the origin.
That is, we consider all monotonic functions G : R [special characters omitted] R such that G(0) = 0 and ask, for which G, is there an (1 ± ε)-approximation algorithm for computing ∑i∈[ n] G(mi) for any polylogarithmic ε? We give an algebraic characterization for all such G so that: • for all functions G in our class that satisfy our algebraic condition, we provide a very general and constructive way to derive an efficient (1 ± ε)-approximation algorithm for computing ∑i∈[ n] G(mi) with polylogarithmic memory and single pass over data stream; while • for all functions G in our class that do not satisfy our algebraic characterization, we show a lower bound that requires greater then polylog memory for computing an approximation to ∑ i∈[n] G(mi) by any one-pass streaming algorithm.
Thus, we provide a Zero-One Law for all monotonically increasing G which are zero at the origin. Our results are quite general. As just one illustrative example, our main theorem implies a lower bound for G(x) = (x(x – 1))0.5arctan(x+1), while for a function G(x) = (x( x + 1))0.5 arctan(x +1) our main theorem automatically yields a polylog memory one-pass (1 ± ε)-approximation algorithm for computing ∑ i∈[n] G(mi). For both of these illustrative examples no lower or upper bounds were known. Of course there are just illustrative examples, and there are many others.
To the best of our knowledge, this is the first zero-one law in the streaming model for a wide class of functions, though we suspect that there are many more such laws to be discovered. Surprisingly, our upper bound requires only 4-wise independence and does not need the stronger machinery of Nisan's pseudorandom generators, even though our class captures multiple functions that previously required Nisan's generators. Furthermore, our methods can be extended to the more general models and complexity classes. For example, our main theorem is immediately applicable to a more general model with deletions and larger updates. For instance, we show that the law also holds for (a smaller class) of non-decreasing and symmetric functions (i.e., G( x) = G(–x) and G (0) = 0) which due to negative values allow deletions.
Furthermore, our methods may shed some light on the fascinating open problem posed by Guha and Indyk in 2006. We believe that our methods are quite general and extend to other classes such as sublinear-space functions or distributions (i.e., to the functions G(mi/m)).
