Tracking the median on a sliding window

Tracking the median on a sliding window

Our objective here is to specify an algorithm for tracking the median of the data in a sliding window as it moves along an array. It turns out that one can indeed find the median using O(log(log(window_size)) operations per window slide. Whether this is worth doing is open to question. Here are the details.

Le 2m+1 be the window width. We examine the initial window, sort it, and divide it up into segments (bins). The first and last bins are of length m/2, the second and next last bins are of length m/4, and so until adding yet another pair of bins would reduce the bin size to less than log2(m). For example, if m=64, i.e., the window size is 129, the bin sizes would be

        32, 16, 8, 8, 1, 8, 8, 16, 32  

where the bin of length 1 is the median. In what follows we will use the highest values of the low order bins and the lowest values of the high order bins as bin separators, except that the median is the bin separator for the inner most pair of bins.

Read full article from Tracking the median on a sliding window