For certain types of data, you can achieve constant time median filtering (Perreault et al, 2007).
That paper describes 2D median filtering on images, assuming the pixels are 8-bit integers.
Note that "constant time" refers to constant time in the size of the window; it is not constant time in the size of data, or in the precision (bits) of data. As explained below, using this algorithm with high-precision data will dramatically increase the memory usage by the algorithm, due to the histogram.
Firstly it is necessary to understand multi-level histograms.
- When the alphabet set (the set of allowed pixel values) has 256 symbols, the histogram has 256 bins.
- A multi-level histogram for 256 bins will have two levels. The first level will have 16 bins, and the second level will have the full 256 bins.
- Each of the 16 first-level bin corresponds to some 16 consecutive bins on the second level, in the most straightforward way.
- Each increment (add-sample) operation will increment the bin on the second level, as well as one of the 16 bins on the first level.
- Likewise, decrement (remove-sample) operation will decrement a bin on both the first and second levels.
- When one needs to search for the median, one will first search among the first-level bins, as there are fewer of them. Once the correct first-level bin is found, one will then search among the 16 second-level bins, where it is guaranteed that one of those will contain the median.
- From this, you can see why the algorithm time complexity is proportional to the number of bits in the data precision.
- Then, for each dimension of data, you will maintain the histogram for a sliding window, each time adding one sample and removing one sample.
- If the data has multiple dimensions, then an array of histograms (as many as the width of the input in the first dimension) will need to be maintained.
Obviously this quickly grows out of hand for higher dimensions, but for some combinations of input sizes and window sizes, this scheme turns out to have better performance than previously known approaches.
Whether this algorithm can be used in your application will depend on the type of data you need to sort.
For example, if your data contains 32-bit integers, and all
2^32 different values are equally likely to appear in the data, then you will need a histogram having
2^32 bins, which is a somewhat insane requirement, but might still be doable. If your data contains IEEE double-precision floating point values, and all
1023 * 2^52 values are likely to occur, then the histogram will apparently not fit in any kind of computers currently available.
You can reduce the number of histogram bins needed by lowering the resolution (precision) of your data.