An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits

DOI10.4230/LIPICS.APPROX-RANDOM.2014.531zbMath1359.68291OpenAlexW2284988863MaRDI QIDQ2969645

Jonathan Katzman, Vladimir Braverman, Gregory Vorsanger, Charles Seidell

Publication date: 22 March 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4721/pdf/38.pdf/

zbMATH Keywords

randomized algorithmsstreaming algorithmsfrequency momentsheavy hitters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14) Randomized algorithms (68W20)

Related Items (5)

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 ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ On Approximating Matrix Norms in Data Streams

This page was built for publication: An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits