Towards Optimal Moment Estimation in Streaming and Distributed Models

DOI10.1145/3596494OpenAlexW2979234330MaRDI QIDQ6051992

Rajesh Jayaram, David P. Woodruff

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3596494

zbMATH Keywords

message passingmoment estimationstreaming

Mathematics Subject Classification ID

Computer science (68-XX)

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
• Corrigendum to: ``A second look at counting triangles in graph streams
• Randomized algorithms for tracking distributed count, frequencies, and ranks
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Zero-one frequency laws
• Computational Advertising: Techniques for Targeting Relevant Ads
• An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits
• 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
• Compressed Counting
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Continuous Monitoring of l_p Norms in Data Streams
• Univariate Stable Distributions
• The Data Stream Space Complexity of Cascaded Norms
• Optimal principal component analysis in distributed and streaming models
• Tighter Low-rank Approximation via Sampling the Leveraged Element
• Relative Errors for Deterministic Low-Rank Matrix Approximations
• 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
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

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