Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees

DOI10.1007/11940128_5MaRDI QIDQ5459099zbMATH OpenOpenAlexFDO

Authors Tobias Lenz

Publication date 24 April 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11940128_5

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• Finding median in read-only memory on integer input
• The shifting sands algorithm
• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• An \(\Omega(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})\) space lower bound for finding \(\epsilon \)-approximate quantiles in a data stream
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams

This page was built for publication: Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees

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