Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element

Lemire, Daniel (2006). « Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element ». Nordic Journal of Computing, 13(4), pp. 328-339.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (158kB)

Résumé

The running maximum-minimum (max-min) filter computes the maxima and minima over running windows of size w. This filter has numerous applications in signal processing and time series analysis. We present an easy-to-implement online algorithm requiring no more than 3 comparisons per element, in the worst case. Comparatively, no algorithm is known to compute the running maximum (or minimum) filter in 1.5 comparisons per element, in the worst case. Our algorithm has reduced latency and memory usage.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	Streaming algorithm, Maximum-Minimum Filter
Unité d'appartenance:	Télé-université > UER Science et Technologie
Déposé par:	Daniel Lemire
Date de dépôt:	05 juin 2007
Dernière modification:	01 nov. 2014 02:03
Adresse URL :	http://archipel.uqam.ca/id/eprint/309

Modifier les métadonnées (propriétaire du document)

Statistiques