EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Novel Optimal Segmentation Algorithm for Large-Scale Time Series Applications

Chi-Jen Wu, Wei-Sheng Zeng, Jan-Ming Ho, Jerry Chun-Wei Lin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →