Taylor Polynomial Estimator for Estimating Frequency Moments
From MaRDI portal
Publication:3448814
DOI10.1007/978-3-662-47672-7_44zbMath1441.68284arXiv1506.01442OpenAlexW2963416264MaRDI QIDQ3448814
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
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
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
