The shifting sands algorithm
Andrew McGregor, Paul Valiant · 2012
We resolve the problem of small-space approximate selection in random-order streams. Specifically, we present an algorithm that reads the n elements of a set in random order and returns an element whose rank differs from the true median by at most n 1/3+o(1) while storing a constant number of elements and counters at any one time. This is optimal: it was previously shown that achieving better accuracy required poly(n) memory. However, it was conjectured that the lower bound was not tight and that a previous algorithm achieving an n 1/2+o(1) approximation was optimal. We therefore consider the new result a surprising resolution to a natural and basic question. 1