Streaming sums in sublinear space.

摘要: Given a stream $S$ of length $m$ with element frequencies $f_i$, $i\in[n]$, and function ${g:\mathbb{N}\to\mathbb{R}}$, we consider the problem computing $(1\pm\epsilon)$-approximation to $\sum g(f_i)$. Most previous efforts have focused on specific functions, for example $p$-th moment $g(x)=|x|^p$ or other norms. The main contributions this paper are complete classification space necessary approximating periodic decreasing up polylogarithmic factors, sublinear algorithm non-monotone functions satisfying relatively simple sufficient condition. This is first streaming complexity characterization that not just monotonically increasing, it improvement general frequency sums since 2010. Our sharpest results characterize nonincreasing in terms domain size \emph{and} length. In contrast approximations moments, turns out storage required approximate depends delicately stream. We apply our derive sublinear-space harmonic mean, geometric cumulative histogram frequencies.