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

DOI10.1007/978-3-642-14553-7_11MaRDI QIDQ3587339zbMATH OpenOpenAlexFDO

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

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)

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)

Cited in

(6)

• 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
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Approximate aggregation for tracking quantiles in wireless sensor networks
• 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)