An optimal algorithm for large frequency moments using O(n^1-2/k) bits
From MaRDI portal
Publication:2969645
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
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
- The value of multiple read/write streams for approximating frequency moments
- Continuous monitoring of \(\ell_p\) norms in data streams
- High probability frequency moment sketches
- 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)
