Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams

DOI10.1137/07069328XMaRDI QIDQ3642875zbMATH OpenFDO

Authors Sudipto Guha, Andrew McGregor

Publication date 6 November 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/07069328X

zbMATH Keywords

communication complexitystochastically generated streamsstream computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Revisiting frequency moment estimation in random order streams
• Robust lower bounds for communication and stream computation
• The shifting sands algorithm
• Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams

Cited in

(18)

• The shifting sands algorithm
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Statistical estimation with bounded memory
• Variable selection for distributed sparse regression under memory constraints
• A randomized online quantile summary in \(O(\frac 1\varepsilon\log\frac 1\varepsilon)\) words
• Robust lower bounds for communication and stream computation
• A randomized online quantile summary in O((1/) (1/)) words
• Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees
• Parameter estimation of linear mixed effects model based on online update
• Verifiable stream computation and Arthur-Merlin communication
• Global debiased DC estimations for biased estimators via pro forma regression
• Quantile regression under memory constraint
• Superlinear lower bounds for multipass graph processing
• A second look at counting triangles in graph streams
• Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
• Frugal Streaming for Estimating Quantiles
• Revisiting frequency moment estimation in random order streams
• Weighted matching in the random-order streaming and robust communication models

This page was built for publication: Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams

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