An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

Simple item page
dc.creatorLemire, Daniel
dc.creatorBrooks, Martin
dc.creatorYan, Yuhong
dc.date2007-02-24
dc.date.accessioned2026-07-07T07:48:40Z
dc.date.available2026-07-07T07:48:40Z
dc.descriptionMonotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array 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, present an optimal linear time algorithm based on novel formalism, and compare experimentally its performance to a linear time top-down regression algorithm. We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.
dc.descriptionAppeared in ICDM 2005
dc.identifierhttps://arxiv.org/abs/cs/0702142
dc.identifierhttp://arxiv.org/abs/cs/0702142
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/124580
dc.subjectData Structures and Algorithms
dc.subjectDatabases
dc.titleAn Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation
dc.typetext

Files

Collections

arXiv