Fast Moment Estimation in Data Streams in Optimal Space

DSpace/Manakin Repository

Fast Moment Estimation in Data Streams in Optimal Space

Citable link to this page

 

 
Title: Fast Moment Estimation in Data Streams in Optimal Space
Author: Kane, Daniel M.; Nelson, Jelani; Porat, Ely; Woodruff, David P.

Note: Order does not necessarily reflect citation order of authors.

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.
Full Text & Related Files:
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.
Published Version: doi:10.1145/1993636.1993735
Other Sources: http://arxiv.org/abs/1007.4191
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:13792657
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters