2026-10-13T23:57:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1695 2024-03-06T10:08:14Z ddc:004 open_access

Lower bound for estimating frequency for update data streams Ganguly, Sumit Data stream lower bound frequency estimation stream automata linear map 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sumit Ganguly 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08341.4 urn:nbn:de:0030-drops-16959 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.4 eng https://creativecommons.org/licenses/by/4.0/legalcode