Now showing items 1-1 of 1

• #### Fast Moment Estimation in Data Streams in Optimal Space ﻿

(ACM, 2011)
We give a space-optimal streaming algorithm with update time $O(log^2(1/\epsilon)loglog(1/\epsilon))$ for approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a data stream up to a factor ...