Ganguly, Sumit
Lower bound for estimating frequency for update data streams
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 ndimensional 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^{22/p}epsilon^{2} log {sigma})$, for $1le p < 2$ and $1/4 le epsilon = Omega(n^{1/21/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 = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum 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 