Running Max/Min Filters using 1+o(1) Comparisons per Sample.

Abstract

A running max (or min) filter asks for the maximum or (minimum) elements within a fixed-length sliding window. The previous best deterministic algorithm (developed by Gil and Kimmel, and refined by Coltuc) can compute the 1D max filter using 1.5+o(1) comparisons per sample in the worst case. The best known algorithm for independent and identically distributed input uses 1.25+o(1) expected comparisons per sample(by Gil and Kimmel). In this work, we show that the number of comparisons can be reduced to 1+o(1) comparisons per sample in the worst case. As a consequence of the new max/min filters, the opening (or closing) filter can also be computed using 1+o(1) comparisons per sample in the worst case, where the previous best work requires 1.5+o(1) comparisons per sample (by Gil and Kimmel); and computing the max and min filters simultaneously can be done in 2+o(1) comparisons per sample in the worst case, where the previous best work (by Lemire) requires 3 comparisons per sample. Our improvements over the previous work are asymptotic, that is, the number of comparisons is reduced only when the window size is large.