License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.573
URN: urn:nbn:de:0030-drops-53248
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5324/
Go to the corresponding LIPIcs Volume Portal

Braverman, Vladimir ; Ostrovsky, Rafail ; Roytman, Alan

Zero-One Laws for Sliding Windows and Universal Sketches

pdf-format:
34.pdf (0.6 MB)

Abstract

Given a stream of data, a typical approach in streaming algorithms is to design a sophisticated algorithm with small memory that computes a specific statistic over the streaming 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 the 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 these 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 unbounded streaming model and the sliding window streaming model.

BibTeX - Entry

@InProceedings{braverman_et_al:LIPIcs:2015:5324,
  author =	{Vladimir Braverman and Rafail Ostrovsky and Alan Roytman},
  title =	{{Zero-One Laws for Sliding Windows and Universal Sketches}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{573--590},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5324},
  URN =		{urn:nbn:de:0030-drops-53248},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.573},
  annote =	{Keywords: Streaming Algorithms, Universality, Sliding Windows}
}

Keywords: Streaming Algorithms, Universality, Sliding Windows
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI