Optimal approximations of the frequency moments of data streams

DOI10.1145/1060590.1060621zbMath1192.68364OpenAlexW2069414131WikidataQ57482527 ScholiaQ57482527MaRDI QIDQ3581423

David P. Woodruff, Piotr Indyk

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Counting distinct items over update streams ⋮ Taylor Polynomial Estimator for Estimating Frequency Moments ⋮ The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Optimal sampling from sliding windows ⋮ Unnamed Item ⋮ Estimating hybrid frequency moments of data streams ⋮ Unnamed Item ⋮ Symmetric norm estimation and regression on sliding windows ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ High Probability Frequency Moment Sketches ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. ⋮ Unnamed Item ⋮ Statistical estimation with bounded memory ⋮ Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Applying approximate counting for computing the frequency moments of long data streams ⋮ Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression ⋮ Sketching information divergences ⋮ How to catch \(L_2\)-heavy-hitters on sliding windows ⋮ A general method for estimating correlated aggregates over a data stream ⋮ Hierarchical sampling from sketches: Estimating functions over data streams ⋮ A Note on Estimating Hybrid Frequency Moment of Data Streams ⋮ On Approximating Matrix Norms in Data Streams ⋮ Space-efficient estimation of statistics over sub-sampled streams