Polynomial Estimators for High Frequency Moments

Details Polynomial Estimators for High Frequency Moments Polynomial Estimators for High Frequency Moments

2011-04-23

arxiv.org/abs/1104.4552v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present an algorithm for computing $F_p$, the $p$th moment of an $n$-dimensional frequency vector of a data stream, for $2 < p < \log (n) $, to within $1\pm \epsilon$ factors, $\epsilon \in [n^{-1/p},1]$ with high constant probability. Let $m$ be the number of stream records and $M$ be the largest magnitude of a stream update. The algorithm uses space in bits $$ O(p^2\epsilon^{-2}n^{1-2/p}E(p,n) \log (n) \log (nmM)/\min(\log (n),\epsilon^{4/p-2}))$$ where, $E(p,n) = (1-2/p)^{-1}(1-n^{-4(1-2/p})$. Here $E(p,n)$ is $ O(1)$ for $p = 2+\Omega(1)$ and $ O(\log n)$ for $p = 2 + O(1/\log (n)$. This improves upon the space required by current algorithms \cite{iw:stoc05,bgks:soda06,ako:arxiv10,bo:arxiv10} by a factor of at least $\Omega(\epsilon^{-4/p} \min(\log (n), \epsilon^{4/p-2}))$. The update time is $O(\log (n))$. We use a new technique for designing estimators for functions of the form $\psi(\expect{X})$, where, $X$ is a random variable and $\psi$ is a smooth function, based on a low-degree Taylor polynomial expansion of $\psi(\expect{X})$ around an estimate of $\expect{X}$.

Affiliated with

Also associated with

No associations

Rating

Polynomial Estimators for High Frequency Moments 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 Polynomial Estimators for High Frequency Moments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Estimators for High Frequency Moments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-484221