Lower bounds on frequency estimation of data streams
Šumit Ganguly · 2008
Abstract. We consider a basic problem in the general data streaming model, namely, to estimate a vector f ∈ Z n that is arbitrarily updated (i.e., incremented or decremented) coordinatewise. The estimate ˆ f ∈ Z n must satisfy ‖ ˆ f − f‖ ∞ ≤ ɛ‖f‖1, that is, ∀i ( | ˆ fi − fi | ≤ ɛ‖f‖1). It is known to have Õ(ɛ−1) randomized space upper bound [4], Ω(ɛ −1 log(ɛn)) space lower bound [2] and deterministic space upper bound of ˜ Ω(ɛ −2) bits. 1 We show that any deterministic algorithm for this problem requires space Ω(ɛ −2 (log‖f‖1)) bits. 1