Fast Moment Estimation in Data Streams in Optimal Space

2010/07/23 by Daniel M. Kane, Jelani Nelson, Kane, Daniel M. +5 · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1007.4191

arxiv created 2010/07/23 · arxiv updated 2010/07/26

Abstract

We give a space-optimal algorithm with update time O(log²(1/eps)loglog(1/eps)) for (1+eps)-approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a data stream. This provides a nearly exponential improvement in the update time complexity over the previous space-optimal algorithm of [Kane-Nelson-Woodruff, SODA 2010], which had update time Omega(1/eps²).

Cited by

• Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
• Unbiased Insights: Optimal Streaming Algorithms for ℓ_p Sampling, the Forget Model, and Beyond

Related

• Estimating small moments of data stream in nearly optimal space-time
• Revisiting Norm Estimation in Data Streams
• On Estimating the First Frequency Moment of Data Streams
• Separations for Estimating Large Frequency Moments on Data Streams
• Polynomial Estimators for High Frequency Moments