A Novel Optimal Segmentation Algorithm for Large-Scale Time Series Applications
IEEE Open Journal of Signal Processing · 2026 · 7 · 809-821
DOI: 10.1109/ojsp.2026.3713804 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Open Journal of Signal Processing, 2026. Verfasst von Chi-Jen Wu und 3 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science and Technology Council.
Abstract (Originalsprache)
When dealing with a time series dataset, a key challenge lies in grasping the dynamic signals. An integral task involves representing the time series through line segments, typically done as a preprocessing step to capture patterns and signals. This paper, however, centers on optimizing the time series segmentation through segmented linear regression models, specifically addressing large-scale datasets. We first formulate the optimization of Multi-Segment Linear Regression (MSLR), which aims to minimize the global square error of the segmented linear representations. The major contribution is that we introduce an optimal MSLR algorithm, denoted as OMSLR, featuring a 2-level dynamic programming structure. We also demonstrate the optimality and the low time complexity of O( $kn^{2}$ ), where $k$ is the number of non-overlapping segments and $n$ is the length of the time series. The results demonstrate that the designed OMSLR matches the optimal global squared error of the classical $O(kn^{3})$ dynamic programming baseline and brute-force search to floating-point precision, while running roughly two orders of magnitude faster at $n = 10{,}000$ and producing lower reconstruction error at every $k$ than the bottom-up, top-down, Sim-Piece, and Mix-Piece baselines. Both effectiveness and efficiency are demonstrated on synthetic series, reference benchmarks, and the UCR time series archive.
Förderung
- National Science and Technology Council
Zitieren
APA
Wu, C., Zeng, W., Ho, J., & Lin, J. C. (2026). A Novel Optimal Segmentation Algorithm for Large-Scale Time Series Applications. IEEE Open Journal of Signal Processing, 7, 809-821. https://doi.org/10.1109/ojsp.2026.3713804
Vancouver
Wu C, Zeng W, Ho J, Lin JC. A Novel Optimal Segmentation Algorithm for Large-Scale Time Series Applications. IEEE Open Journal of Signal Processing. 2026;7:809-821. doi:10.1109/ojsp.2026.3713804
BibTeX
@article{Wu2026,
author = {Wu, Chi-Jen and Zeng, Wei-Sheng and Ho, Jan-Ming and Lin, Jerry Chun-Wei},
title = {A Novel Optimal Segmentation Algorithm for Large-Scale Time Series Applications},
journal = {IEEE Open Journal of Signal Processing},
year = {2026},
volume = {7},
pages = {809--821},
doi = {10.1109/ojsp.2026.3713804}
}
EUVIMED