Fast Computation of the Median by Successive Binning

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

Applications

The following projects currently use an implementation of binmedian or binapprox:

	Cytobank: Cytobank is a web-based program to do flow cytometry data analysis. See http://www.cytobank.org.
	Large Synoptic Survery Telescope (LSST): "LSST is a wide-field telescope facility that will add a qualitatively new capability in astronomy. For the first time, the LSST will provide time-lapse digital imaging of faint astronomical objects across the entire sky." See http://www.lsst.org.

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