Towards Optimal Moment Estimation in Streaming and Distributed Models

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.29OpenAlexW2982180529MaRDI QIDQ5875483

Rajesh Jayaram, David P. Woodruff

Publication date: 3 February 2023

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

zbMATH Keywords

sketchingmessage passingmoment estimationstreaming

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

A Framework for Adversarially Robust Streaming Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-efficient estimation of statistics over sub-sampled streams
• An information statistics approach to data stream and communication complexity
• Approximate counting: a detailed analysis
• Pseudorandom generators for space-bounded computation
• Optimal tracking of distributed heavy hitters and quantiles
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Zero-one frequency laws
• Computational Advertising: Techniques for Targeting Relevant Ads
• Optimal Random Sampling from Distributed Streams Revisited
• Algorithms for distributed functional monitoring
• Sparser Johnson-Lindenstrauss Transforms
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Optimal approximations of the frequency moments of data streams
• Functional Monitoring without Monotonicity
• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
• Counting large numbers of events in small registers
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Continuous Monitoring of l_p Norms in Data Streams
• The Data Stream Space Complexity of Cascaded Norms
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
• Tight bounds for distributed functional monitoring
• Fast moment estimation in data streams in optimal space
• Streaming Algorithms via Precision Sampling

This page was built for publication: Towards Optimal Moment Estimation in Streaming and Distributed Models