Simpler algorithm for estimating frequency moments of data streams

DOI10.1145/1109557.1109634MaRDI QIDQ3581589zbMATH OpenOpenAlexFDO

Authors Lakshminath Bhuvanagiri, Sumit Ganguly, Kesh Deepanjan, Chandan Saha

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1109557.1109634

Mathematics Subject Classification ID

Source coding (94A29)

Cited in

(11)

• Optimal sampling from sliding windows
• Sketching information divergences
• How to catch \(L_2\)-heavy-hitters on sliding windows
• Separations for estimating large frequency moments on data streams
• Applying approximate counting for computing the frequency moments of long data streams
• Efficient online estimation for nonparametric regression models with streaming data
• Taylor polynomial estimator for estimating frequency moments
• Continuous monitoring of _p norms in data streams
• High probability frequency moment sketches
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• The Simultaneous Communication of Disjointness with Applications to Data Streams

This page was built for publication: Simpler algorithm for estimating frequency moments of data streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581589)