Fast minimum-maximal filter in Python
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
LICENSE
README.md
maxmin.py

README.md

pythonmaxmin

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.

Suitability

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.

See also

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

https://github.com/notnot/movingminmax