In 'Selection and Sorting with Limited Storage' [MP78], Munro and Paterson presented results on the selection (median finding) problem. Their model allowed a small number of one-way passes over input stored on a read-ony tape are possible. This paper is now regarded as one of the first works in the streaming model. I will recap the results in [MP78], and discuss two more recent results on this theme: approximate selection on a stream with both 'insertion' and 'deletion' records; and tight lower bounds for multi-pass median finding when the input data is randomly ordered.
This file was generated by bibtex2html 1.92.