An online algorithm for segmenting time series

TLDR

Time‑series mining has grown rapidly, with piecewise linear approximation widely used for clustering, classification, indexing, and association rule mining, yet many algorithms for this representation have been independently rediscovered. This study conducts the first comprehensive review and empirical comparison of all existing piecewise linear approximation techniques. We propose a novel algorithm that outperforms all previously published methods in empirical tests. Our analysis reveals that every existing algorithm has fatal data‑mining flaws.

Abstract

In recent years, there has been an explosion of interest in mining time-series databases. As with most computer science problems, representation of the data is the key to efficient and effective solutions. One of the most commonly used representations is piecewise linear approximation. This representation has been used by various researchers to support clustering, classification, indexing and association rule mining of time-series data. A variety of algorithms have been proposed to obtain this representation, with several algorithms having been independently rediscovered several times. In this paper, we undertake the first extensive review and empirical comparison of all proposed techniques. We show that all these algorithms have fatal flaws from a data-mining perspective. We introduce a novel algorithm that we empirically show to be superior to all others in the literature.