An optimal linear time algorithm for quasi-monotonic segmentation [r-libre/224]

Lemire, Daniel ORCID: https://orcid.org/0000-0003-3306-6922, Brooks, Martin et Yan, Yuhong (2009). An optimal linear time algorithm for quasi-monotonic segmentation. International Journal of Computer Mathematics, 86 (7), 1093-1104. 10.1080/00207160701694153

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

PDF - 0709.1166v1.pdf

Catégorie de document :	Articles de revues
Évaluation par un comité de lecture :	Oui
Étape de publication :	Publié
Résumé :	Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting a sequence in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem using the l_inf norm, and we present an optimal linear time algorithm based on novel formalism. Moreover, given a precomputation in time O(n log n) consisting of a labeling of all extrema, we compute any optimal segmentation in constant time. We compare experimentally its performance to two piecewise linear segmentation heuristics (top-down and bottom-up). We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.
Adresse de la version officielle :	http://www.tandfonline.com/doi/abs/10.1080/0020716...
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	22 juill. 2014 21:50
Dernière modification :	05 nov. 2026 20:33

RÉVISER