2008/01/01 by Šumit Ganguly, Ganguly, Sumit
Computer Science · #Algorithms and Data Compression #Caching and Content Delivery #Cooperative Communication and Network Coding #Data stream #frequency estimation #linear map #lower bound #stream automata
paper · doi:10.4230/dagsemproc.08341.4
openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, fi(sigma) = sum(index,i,v) in sigma v . The n-dimensional vector f(sigma) with ith coordinate fi(sigma) is called the frequency vector of the stream sigma. We consider the problem of finding an n-dimensional integer vector hatf(sigma) that estimates the frequency vector f(sigma) of an input stream sigma in the following sense: ormhatf (sigma)- f(sigma) le epsilon ormf(sigma)p For p=1 and 2, there are randomized algorithms known with space bound ildeO(epsilon-p). A space lower bound of Omega(epsilon-1 log (nepsilon)) is also known. However, the deterministic space upper bound is ildeO(epsilon-2). In this work, we present a deterministic space lower bound of Omega(n2-2/pepsilon-2 log |sigma|), for 1le p < 2 and 1/4 le epsilon = Omega(n1/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.