Towards Optimal Moment Estimation in Streaming and Distributed Models

DOI10.4230/LIPICS.APPROX-RANDOM.2019.29MaRDI QIDQ5875483zbMATH OpenOpenAlexFDO

Authors Rajesh Jayaram, David P. Woodruff

Publication date 3 February 2023

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

zbMATH Keywords

message passingmoment estimationsketchingstreaming

Mathematics Subject Classification ID

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

Cites work

• 1-pass relative-error L_p-sampling with applications
• A near-optimal algorithm for estimating the entropy of a stream
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Algorithms for distributed functional monitoring
• An information statistics approach to data stream and communication complexity
• Approximate counting: a detailed analysis
• Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
• Continuous monitoring of _p norms in data streams
• Counting large numbers of events in small registers
• Data streams: algorithms and applications.
• Fast moment estimation in data streams in optimal space
• Functional Monitoring without Monotonicity
• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
• scientific article; zbMATH DE number 1256715 (Why is no real title available?)
• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• On the exact space complexity of sketching and streaming small norms
• Optimal approximations of the frequency moments of data streams
• Optimal Random Sampling from Distributed Streams Revisited
• Optimal space lower bounds for all frequency moments
• Optimal tracking of distributed heavy hitters and quantiles
• Pseudorandom generators for space-bounded computation
• Revisiting frequency moment estimation in random order streams
• Robust lower bounds for communication and stream computation
• Sketching as a tool for numerical linear algebra
• Space-efficient estimation of statistics over sub-sampled streams
• Sparser Johnson-Lindenstrauss transforms
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Streaming algorithms via precision sampling
• The Data Stream Space Complexity of Cascaded Norms
• The one-way communication complexity of Hamming distance
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Tight bounds for distributed functional monitoring
• Zero-one frequency laws

Cited in

(2)

• A Framework for Adversarially Robust Streaming Algorithms
• Separations for estimating large frequency moments on data streams

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875483)