License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-16959
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1695/

Ganguly, Sumit

Lower bound for estimating frequency for update data streams

pdf-format:
Dokument 1.pdf (292 KB)


Abstract

We consider general update streams, where, the stream is a sequence of updates of the form $(index, i, v)$, where, $i in {1,2 ldots, n}$ and $v in {-1,+1}$, signifying deletion or insertion, respectively of an instance of $i$. The frequency of $i in {1,2,ldots, n}$ is given as the sum of the updates to $i$, that is, $f_i(sigma) = sum_{(index,i,v) in sigma} v $. The $n$-dimensional vector $f(sigma)$ with $i$th coordinate $f_i(sigma)$ is called the frequency vector of the stream $sigma$. We consider the problem of finding an n-dimensional integer vector $hat{f}(sigma)$ that estimates the frequency vector $f(sigma)$ of an input stream $sigma$ in the following sense: orm{hat{f} (sigma)- f(sigma)} le epsilon orm{f(sigma)}_p For $p=1$ and $2$, there are randomized algorithms known with space bound $ ilde{O}(epsilon^{-p})$. A space lower bound of $Omega(epsilon^{-1} log (nepsilon))$ is also known. However, the deterministic space upper bound is $ ilde{O}(epsilon^{-2})$. In this work, we present a deterministic space lower bound of $Omega(n^{2-2/p}epsilon^{-2} log |{sigma}|)$, for $1le p < 2$ and $1/4 le epsilon = Omega(n^{1/2-1/p})$. For $p ge 2$, we show an $Omega(n)$ space lower bound for all $epsilon < 1/4$. The results are obtained using a new characterization of data stream computations, that show that any uniform computation over a data stream may be viewed as an appropriate linear map.

BibTeX - Entry

@InProceedings{ganguly:DSP:2008:1695,
  author =	{Sumit Ganguly},
  title =	{Lower bound for estimating frequency for update data streams},
  booktitle =	{Sublinear Algorithms },
  year =	{2008},
  editor =	{Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler},
  number =	{08341},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1695},
  annote =	{Keywords: Data stream, lower bound, frequency estimation, stream automata, linear map}
}

Keywords: Data stream, lower bound, frequency estimation, stream automata, linear map
Seminar: 08341 - Sublinear Algorithms
Issue date: 2008
Date of publication: 25.11.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI