Fast minimum-maximal filter in Python
This code implements the algorithms described in the following paper:
Daniel Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element. Nordic Journal of Computing, 13 (4), pages 328-339, 2006.
A preprint is available there:
http://arxiv.org/abs/cs.DS/0610046
The main algorithm presented in this package is used in Apache Hive.
The new algorithm introduced in the manuscript is most suitable for piecewise monotonic data or when low-latency is required. Otherwise, Gil-Kimmel and van Herk are good choices.
For an application in C++: https://github.com/lemire/runningmaxmin
For an application of this idea to rolling statistics in JavaScript, see
https://github.com/shimondoodkin/efficient-rolling-stats
For an application in Go, please see