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

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

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

(29)

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

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)