Binmedian and binapprox are algorithms to compute the median, resp. an approximation to the median. Binmedian has O(n) average running time and binapprox has O(n) worst-case running time. These algorithms are highly competitive with the standard algorithm---quickselect---when computing the median of a single data set, but are significantly faster in updating the median when more data is added. Furthermore, their strategies are able to be parallelized/distributed, and are hence suitable for use in something like a wireless sensor network.

Click here for the paper.

Here is some sample code that implements binmedian, binapprox, and quickselect. This code is intended for demonstration purposes only (the n even case for binmedian is not implemented yet).

Fortran code: | binmedian.f | binapprox.f | quickselect.f |

C code: | binmedian.c | binapprox.c | quickselect.c |

Click here to go back to Ryan's research page.