License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-16959
URL:

Lower bound for estimating frequency for update data streams

 pdf-format:

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 Related Scholarly Article: Issue date: 2008 Date of publication: 2008

DROPS-Home | Fulltext Search | Imprint