Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees

DOI10.1007/11940128_5zbMATH Open1135.68380OpenAlexW1523320941MaRDI QIDQ5459099FDOQ5459099

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

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

Mathematics Subject Classification ID

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

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)