| DOI | Resolve DOI: https://doi.org/10.1080/00207160701694153 |
|---|
| Author | Search for: Lemire, Daniel1; Search for: Brooks, Martin1; Search for: Yan, Yuhong1 |
|---|
| Affiliation | - National Research Council of Canada. NRC Institute for Information Technology
|
|---|
| Format | Text, Article |
|---|
| Subject | time series; segmentation; monotonicit; design of algorithms |
|---|
| Abstract | Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting a sequence in up to K segments. We want the segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem using the l ∞ norm, and we present an optimal linear time algorithm based on a novel formalism. Moreover, given a precomputation in time O(n log n) consisting of a labelling 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 modelling. |
|---|
| Publication date | 2009-06-17 |
|---|
| Publisher | Wiley |
|---|
| In | |
|---|
| Language | English |
|---|
| Peer reviewed | Yes |
|---|
| NPARC number | 23004493 |
|---|
| Export citation | Export as RIS |
|---|
| Report a correction | Report a correction (opens in a new tab) |
|---|
| Record identifier | e62c9fa0-5c3f-447b-8a99-7013b20cdf8c |
|---|
| Record created | 2018-11-08 |
|---|
| Record modified | 2020-04-16 |
|---|
