**
Zero-one Frequency Laws.
**

*
Vladimir Braverman, Rafail Ostrovsky
*

**
Abstract:
**

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}(^{mi}) 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(ο) = ο and G can be computed in poly-logarithmic time and space and ask, for which G in this class is there an (± ε)-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 (± ε)-approximation algorithm for computing Σ
_{i∈}|n|^{G}(^{mi}) 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}(^{mi}) by any one-pass streaming algorithm.

**comment:**
STOC 2010

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |