Fast Moment Estimation in Data Streams in Optimal Space
Kane, Daniel M.
Woodruff, David P.
MetadataShow full item record
CitationKane, Daniel M., Jelani Nelson, Ely Porat, and David P. Woodruff. 2011. "Fast Moment Estimation in Data Streams in Optimal Space." In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing: STOC '11, June 6-8, 2011, San Jose, CA: 745-754. New York, NY: ACM.
AbstractWe 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 of \(1 \pm \epsilon\). This provides a nearly exponential improvement over the previous space optimal algorithm of [Kane-Nelson-Woodruff, SODA 2010], which had update time \(\Omega(1/\epsilon^2)\). When combined with the work of [Harvey-Nelson-Onak, FOCS 2008], we also obtain the first algorithm for entropy estimation in turnstile streams which simultaneously achieves near-optimal space and fast update time.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:13792657
- FAS Scholarly Articles