Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)

DOI10.1007/978-3-540-79709-8_22MaRDI QIDQ3503639zbMATH OpenOpenAlexFDO

Authors Sumit Ganguly

Publication date 5 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79709-8_22

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Deterministically Estimating Data Stream Frequencies
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Optimal space lower bounds for all frequency moments
• Optimal approximations of the frequency moments of data streams
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cited in

(13)

• Streaming algorithms with one-sided estimation
• An \(\Omega(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})\) space lower bound for finding \(\epsilon \)-approximate quantiles in a data stream
• Data Stream Algorithms via Expander Graphs
• On Finding Frequent Elements in a Data Stream
• Deterministically Estimating Data Stream Frequencies
• Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
• Precision vs confidence tradeoffs for \(\ell_2\)-based frequency estimation in data streams
• Revisiting frequency moment estimation in random order streams
• Deterministic heavy hitters with sublinear query time
• Buffered Count-Min Sketch on SSD: Theory and Experiments
• Optimality of linear sketching under modular updates
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• Deterministic sparse Fourier transform with an _ guarantee

This page was built for publication: Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)

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