An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

Details An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

2007-09-07

arxiv.org/abs/0709.1166v1

Daniel Lemire, Martin Brooks and Yuhong Yan, An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation. International

Computer Science

Databases

This is the extended version of our ICDM'05 paper (arXiv:cs/0702142)

Scientific paper

10.1080/00207160701694153

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.

Affiliated with

Also associated with

No associations

Rating

An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44157