An (1 1) space lower bound for finding -approximate quantiles in a data stream

DOI10.1007/978-3-642-14553-7_11zbMATH Open1288.68121OpenAlexW2299877023MaRDI QIDQ3587339FDOQ3587339

Authors: Regant Y. S. Hung, H. F. Ting 

Publication date: 7 September 2010

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14553-7_11

Recommendations

• A randomized online quantile summary in \(O((1/\varepsilon) \log(1/\varepsilon))\) words
• A randomized online quantile summary in \(O(\frac 1\varepsilon\log\frac 1\varepsilon)\) words
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Streaming Algorithms Measured in Terms of the Computed Quantity
• Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cited In (6)

• Approximate aggregation for tracking quantiles in wireless sensor networks
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• A randomized online quantile summary in \(O(\frac 1\varepsilon\log\frac 1\varepsilon)\) words
• A randomized online quantile summary in \(O((1/\varepsilon) \log(1/\varepsilon))\) words
• Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees
• Mining frequent items in data stream using time fading model

This page was built for publication: An \(\Omega(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})\) space lower bound for finding \(\epsilon \)-approximate quantiles in a data stream

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