Further Analysis of the Remedian Algorithm

We present an analysis of the remedian, an efficient, known algorithm, for the approximate median selection problem, that is easy to implement. The algorithm can be used for data in an array, as well as for streaming data. In an array it performs in-place, recursively dividing the candidate values into sets of size b, from which exact medians are selected for the next phase. On streaming data it performs a filter operation, requiring, by the time n items are processed, the storage of log(b) n candidate entries. The contribution of the article is a precise characterization, combinatorial and asymptotic, of the accuracy of the algorithm, showing explicitly the role of the critical design parameter b. In addition, we compute the time and space costs of the algorithm, and present experimental illustrations of its accuracy.