Publication: Fast Moment Estimation in Data Streams in Optimal Space
Loading...
Open/View Files
Date
2011
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
ACM
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Kane, 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.
Abstract
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 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.
Description
Other Available Sources
Research Data
Keywords
algorightm, theory, data stream algorightm, frequency moments
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service