Fast moment estimation in data streams in optimal space

DOI10.1145/1993636.1993735zbMath1288.68269arXiv1007.4191OpenAlexW2113623631MaRDI QIDQ5419145

David P. Woodruff, Daniel M. Kane, Ely Porat, Jelani Nelson

Publication date: 5 June 2014

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

Full work available at URL: https://arxiv.org/abs/1007.4191

zbMATH Keywords

frequency momentsdata stream algorithms

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (16)

Sparser Johnson-Lindenstrauss Transforms ⋮ Evaluating Bayesian Networks via Data Streams ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tracking the l_2 Norm with Constant Update Time ⋮ High Probability Frequency Moment Sketches ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Fingerprints for highly similar streams ⋮ Streaming pattern matching with \(d\) wildcards ⋮ Unnamed Item ⋮ Real-Time Streaming Multi-Pattern Search for Constant Alphabet ⋮ On Approximating Matrix Norms in Data Streams ⋮ Tight Bounds for the Subspace Sketch Problem with Applications ⋮ Unnamed Item

This page was built for publication: Fast moment estimation in data streams in optimal space