Revisiting Frequency Moment Estimation in Random Order Streams

Vladimir Braverman, Emanuele Viola, David Woodruff +1

We revisit one of the classic problems in the data stream literature, namely, that of estimating the frequency moments $F_p$ for $0<p<2$ of an underlying $n$-dimensional vector…