An optimal algorithm for large frequency moments using O(n^1-2/k) bits
From MaRDI portal
Publication:2969645
DOI10.4230/LIPICS.APPROX-RANDOM.2014.531zbMATH Open1359.68291OpenAlexW2284988863MaRDI QIDQ2969645FDOQ2969645
Authors: Vladimir Braverman, Jonathan Katzman, Charles Seidell, Gregory Vorsanger 
Publication date: 22 March 2017
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4721/pdf/38.pdf/
Recommendations
- Optimal approximations of the frequency moments of data streams
- An improved data stream algorithm for frequency moments
- Optimal space lower bounds for all frequency moments
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximating Large Frequency Moments with Pick-and-Drop Sampling
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Distributed systems (68M14)
Cited In (13)
- The space complexity of approximating the frequency moments
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- On approximating matrix norms in data streams
- An improved data stream algorithm for frequency moments
- Generalizing the layering method of Indyk and Woodruff: recursive sketches for frequency-based vectors on streams
- Optimal space lower bounds for all frequency moments
- Taylor polynomial estimator for estimating frequency moments
- Universal sketches for the frequency negative moments and other decreasing streaming sums
- Continuous monitoring of \(\ell_p\) norms in data streams
- High probability frequency moment sketches
- The value of multiple read/write streams for approximating frequency moments
- Optimal approximations of the frequency moments of data streams
- The Simultaneous Communication of Disjointness with Applications to Data Streams
This page was built for publication: An optimal algorithm for large frequency moments using \(O(n^{1-2/k})\) bits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969645)
