High Probability Frequency Moment Sketches
From MaRDI portal
Publication:5002734
DOI10.4230/LIPIcs.ICALP.2018.58zbMath1499.68412arXiv1805.10885OpenAlexW2964153476MaRDI QIDQ5002734
David P. Woodruff, Sumit Ganguly
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1805.10885
Online algorithms; streaming algorithms (68W27) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (2)
A Framework for Adversarially Robust Streaming Algorithms ⋮ Tight Bounds for the Subspace Sketch Problem with Applications
Cites Work
- Unnamed Item
- Unnamed Item
- The space complexity of approximating the frequency moments
- Nonparametric goodness-of-fit testing under Gaussian models
- Finding frequent items in data streams
- A Tight Lower Bound for High Frequency Moment Estimation with Small Error
- Computational Advertising: Techniques for Targeting Relevant Ads
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- The Simultaneous Communication of Disjointness with Applications to Data Streams
- Maximum Matching in Turnstile Streams
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Optimal approximations of the frequency moments of data streams
- Simpler algorithm for estimating frequency moments of data streams
- Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
- On Sketching Matrix Norms and the Top Singular Vector
- Fast moment estimation in data streams in optimal space
- How robust are linear sketches to adaptive inputs?
- Compressed sensing
This page was built for publication: High Probability Frequency Moment Sketches
