Universal sketches for the frequency negative moments and other decreasing streaming sums

Vladimir Braverman, Stephen R. Chestnut

Given a stream with frequencies $f_d$, for $d\in [n]$, we characterize the space necessary for approximating the frequency negative moments $F_p=\sum |f_d{|}^p$, where $p<0$ and the s…