Open access research
publication repository

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

Lemire, Daniel; Brooks, Martin, & Yan, Yuhong (2009). An optimal linear time algorithm for quasi-monotonic segmentation. International Journal of Computer Mathematics, 86 (7). https://doi.org/10.1080/00207160701694153

File(s) available for this item:
[img]  PDF - 0709.1166v1.pdf  
Item Type: Journal Articles
Refereed: Yes
Status: Published
Abstract: 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.
Official URL: https://www.tandfonline.com/doi/abs/10.1080/0020716...
Depositor: Lemire, Daniel
Owner / Manager: Daniel Lemire
Deposited: 22 Jul 2014 21:50
Last Modified: 16 Jul 2015 00:47

Actions (login required)