On Estimating Frequency Moments of Data Streams

DOI10.1007/978-3-540-74208-1_35MaRDI QIDQ3603488zbMATH OpenOpenAlexFDO

Authors Sumit Ganguly, Graham Cormode

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_35

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Theory of data (68P99)

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Optimal approximations of the frequency moments of data streams
• Estimating hybrid frequency moments of data streams
• Taylor polynomial estimator for estimating frequency moments
• Estimating Hybrid Frequency Moments of Data Streams

Cited in

(28)

• Zero-one frequency laws
• Sparsifying count sketch
• Fast moment estimation in data streams in optimal space
• Learned sketches for frequency estimation
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Deterministically Estimating Data Stream Frequencies
• A Note on Estimating Hybrid Frequency Moment of Data Streams
• Algorithms - ESA 2003
• Estimating hybrid frequency moments of data streams
• A sketch algorithm for estimating two-way and multi-way associations
• AMS without 4-wise independence on product domains
• Hierarchical sampling from sketches: Estimating functions over data streams
• Estimating Hybrid Frequency Moments of Data Streams
• Sketching information divergences
• A general method for estimating correlated aggregates over a data stream
• Unbiased estimation of inner product via higher order count sketch
• Generalizing the layering method of Indyk and Woodruff: recursive sketches for frequency-based vectors on streams
• The eternal sunshine of the sketch data structure
• Efficient online estimation for nonparametric regression models with streaming data
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Taylor polynomial estimator for estimating frequency moments
• Streaming algorithms via precision sampling
• Tight lower bound for linear sketches of moments
• Continuous monitoring of _p norms in data streams
• High probability frequency moment sketches
• Frugal Streaming for Estimating Quantiles
• Periodicity and cyclic shifts via linear sketches
• An improved data stream summary: the count-min sketch and its applications

This page was built for publication: On Estimating Frequency Moments of Data Streams

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