Now showing items 1-1 of 1

    • Fast Moment Estimation in Data Streams in Optimal Space 

      Kane, Daniel M.; Nelson, Jelani; Porat, Ely; Woodruff, David P. (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 ...