Towards Optimal Moment Estimation in Streaming and Distributed Models

DOI10.1145/3596494MaRDI QIDQ6051992zbMATH OpenOpenAlexWikidataFDO

Authors 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

• 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
• An optimal algorithm for large frequency moments using \(O(n^{1-2/k})\) bits
• Approximate counting: a detailed analysis
• Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
• Compressed counting
• Continuous monitoring of _p norms in data streams
• Corrigendum to: ``A second look at counting triangles in graph 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 principal component analysis in distributed and streaming models
• 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
• Randomized algorithms for tracking distributed count, frequencies, and ranks
• Relative errors for deterministic low-rank matrix approximations
• 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
• Tighter low-rank approximation via sampling the leveraged element
• Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering
• Univariate stable distributions. Models for heavy tailed data
• Zero-one frequency laws

Cited in

(2)

• Finding missing items requires strong forms of randomness
• Improved sublinear-time moment estimation using weighted sampling

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 Q6051992)