Paper Info
Title
Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)
Abstract
We consider a basic problem in the general data streaming model, namely, to estimate a vector [(O)\tilde](e</font >-</font >1)\tilde{O}(\epsilon^{-1}) randomized space upper bound [6], Ω(ε − 1 log(εn)) space lower bound [4] and deterministic space upper bound of [(W</font >)\tilde](e</font >-</font >2)\tilde{\Omega}(\epsilon^{-2}) bits. We show that any deterministic algorithm for this problem requires space bits.
Year
DOI
Venue
2008
10.1007/978-3-540-79709-8_22
CSR
Keywords
Field
DocType
upper bound,lower bound
Discrete mathematics,Data stream mining,Combinatorics,Upper and lower bounds,Tilde,Omega,Deterministic algorithm,Mathematics
Conference
Citations 
PageRank 
References 
6
0.44
13
Authors
1
Name
Order
Citations
PageRank
Sumit Ganguly1813236.01