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