Estimating small moments of data stream in nearly optimal space-time

For each $p\in (0,2]$, we present a randomized algorithm that returns an $ϵ$-approximation of the $p$th frequency moment of a data stream $F_p = \sum_{i = 1}^n \abs{f_i}^p$\mathrm{.}Thealgorithmrequiresspace$O(\epsilon^{-2} \log (mM)(\log n))$andprocesseseachstreamupdateusingtime$O((\log n) (\log \epsilon^{-1}))$\mathrm{.}Itisnearlyoptimalintermsofspace(lowerbound$O(\epsilon^{-2} \log (mM))$ as well as time and is the first algorithm with these properties. The technique separates heavy hitters from the remaining items in the stream using an appropriate threshold and estimates the contribution of the heavy hitters and the light elements to $F_p$ separately. A key component is the design of an unbiased estimator for $\text{abs}{f_i}^p$ whose data structure has low update time and low variance.