Zero− laws for Sliding Windows and Universal Sketches
Braverman Vladimir; Ostrovsky Rafail; Roytman Alan
Abstract:
Given stream of data a typical approach in streaming algorithms is to design a sophisticated algorithm with small memory the computes a specific statistic over the streamlining data. Usually, if one wants to compute a different statistic after the stream is gone, it is impossible. But what if we want to compute a different statistic after the fact? In this paper, we consider the following fascinating possibility: can we collect some small amount of specific data during the stream that is “universal.” i.e., where we do not know anything about the statistics we will want to later compute, other than guarantee that had we known the statistic ahead of time, it would have been possible to do so with small memory? This is indeed what we introduce (and show)in this paper with matching upper and lower bounds: we show that it is possible to collect universal statistics of polylogarithmic size, and prove that this universal statistics allow us after the fact to compute all other statistics that are computable with similar amounts of memory. We show that this is indeed possible, both for the standard on bounded streaming model and the sliding windows streaming model.
comment: CRYOPTO 2015 PP: 573−590
Fetch PDF file of the paper
| Back to Publications List |