STOC Conference 2010 Conference Paper
- Vladimir Braverman
- Rafail Ostrovsky
Data streams emerged as a critical model for multiple applications that handle vast amounts of data. One of the most influential and celebrated papers in streaming is the "AMS" paper on computing frequency moments by Alon, Matias and Szegedy. The main question left open (and explicitly asked) by AMS in 1996 is to give the precise characterization for which functions G on frequency vectors m i (1≤ i ≤ n) can Σ i∈ [n] G(m i ) be approximated efficiently, where "efficiently" means by a single pass over data stream and poly-logarithmic 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 → R such that G(0) = 0 and G can be computed in poly-logarithmic time and space and ask, for which G in this class is there an (1±ε)-approximation algorithm for computing Σ i∈ [n] G(m i ) 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(m i ) with polylogarithmic memory and a 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(m i ) by any one-pass streaming algorithm. Thus, we provide a zero-one law for all monotonically increasing functions 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.5arctan(x+1) our main theorem automatically yields a polylog memory one-pass (1±ε)-approximation algorithm for computing Σ i∈ [n] G(m i ). For both of these examples no lower or upper bounds were known. Of course, these are just illustrative examples, and there are many others. One might argue that these two functions may not be of interest in practical applications -- we stress that our law works for all functions in this class, and the above examples illustrate the power of our method. 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, we believe that our methods can be extended to the more general models and complexity classes. For instance, 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.