Computer Science – Data Structures and Algorithms
Scientific paper
2011-12-31
Computer Science
Data Structures and Algorithms
5 pages
Scientific paper
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}) < \epsilon < 1, the problem of estimating Fp is to estimate \norm{x}_p^p = \sum_{i \in [n]} \abs{x(i)}^p correctly to within a relative accuracy of 1\pm \epsilon 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(n^{1-2/p} \epsilon^{-2/p}+ n^{1-2/p}\epsilon^{-4/p}/ \log^{O(1)}(n)+ (\epsilon^{-2} + \log (n))). The first term in the lower bound expression was proved in \cite{B-YJKS:stoc02,cks:ccc03}, the second in \cite{wz:arxiv11} and the third in \cite{wood:soda04}. In this note, we show an Omega(p^2 n^{1-2/p} \epsilon^{-2}/\log (n)) bits space bound, for Omega(pn^{-1/p}) \le \epsilon \le 1/10.
No associations
LandOfFree
A Lower Bound for Estimating High Moments of a Data Stream does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Lower Bound for Estimating High Moments of a Data Stream, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Lower Bound for Estimating High Moments of a Data Stream will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-673295