2011/12/31 by Sumit Ganguly, Ganguly, Sumit · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1201.0253
5 pages
arxiv created 2011/12/31 · arxiv updated 2015/03/19
We show an improved lower bound for the Fp estimation problem in a data stream setting for p>2. A data stream is a sequence of items from the domain [n] with possible repetitions. The frequency vector x is an n-dimensional non-negative integer vector x such that x(i) is the number of occurrences of i in the sequence. Given an accuracy parameter Omega(n-1/p) < ε< 1, the problem of estimating Fp is to estimate \normxpp = ∑i ∈ [n] \absx(i)p correctly to within a relative accuracy of 1± εwith high constant probability in an online fashion and using as little space as possible. The current space lower bound for this problem is Omega(n1-2/p ε-2/p+ n1-2/pε-4/p/ logO(1)(n)+ (ε-2 + log (n))). The first term in the lower bound expression was proved in \citeB-YJKS:stoc02,cks:ccc03, the second in \citewz:arxiv11 and the third in \citewood:soda04. In this note, we show an Omega(p2 n1-2/p ε-2/log (n)) bits space bound, for Omega(pn-1/p) ≤ ε≤ 1/10.