The shifting sands algorithm

MaRDI QIDQ5743412zbMATH OpenFDO

Authors Andrew McGregor, Paul Valiant

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095155

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Finding median in read-only memory on integer input
• scientific article; zbMATH DE number 1629859
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
• Comparison-based time-space lower bounds for selection

Cites work

• scientific article; zbMATH DE number 5764792 (Why is no real title available?)
• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• scientific article; zbMATH DE number 5485578 (Why is no real title available?)
• Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
• Selection and sorting with limited storage
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams

Cited in

(4)

• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
• Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees
• Approximate sorting of data streams with limited storage
• Lightweight approximate selection

This page was built for publication: The shifting sands algorithm

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