Taylor Polynomial Estimator for Estimating Frequency Moments

DOI10.1007/978-3-662-47672-7_44zbMath1441.68284arXiv1506.01442OpenAlexW2963416264MaRDI QIDQ3448814

Sumit Ganguly

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Point estimation (62F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (4)

Continuous Monitoring of l_p Norms in Data Streams ⋮ Approximating Approximate Pattern Matching ⋮ Quantum Chebyshev's Inequality and Applications ⋮ On Approximating Matrix Norms in Data Streams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• Hierarchical sampling from sketches: Estimating functions over data streams
• The space complexity of approximating the frequency moments
• Finding frequent items in data streams
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Optimal approximations of the frequency moments of data streams
• Simpler algorithm for estimating frequency moments of data streams
• Online Learning of Noisy Data
• Tight Lower Bound for Linear Sketches of Moments
• Tight bounds for distributed functional monitoring
• Lower Bounds for Sparse Recovery
• Streaming Algorithms via Precision Sampling
• (1 + eps)-Approximate Sparse Recovery

This page was built for publication: Taylor Polynomial Estimator for Estimating Frequency Moments