CaT: A Rapid and Precise Algorithm for Piecewise Linear Representation of Time Series
Truong Son Pham · 2024
Time series segmentation is a critical task in many domains, including finance, healthcare, security, and environmental monitoring. Despite its importance, traditional segmentation methods such as Sliding Window and Bottom-Up often fall short in terms of accuracy and computational efficiency, particularly when applied to large and complex datasets. The Top-Down approach, while accurate, is notoriously computationally intensive, limiting its practicality in real-time applications. In this paper, we propose a novel segmentation method, CaT (Candidate-based Top-down), which leverages statistical insights to efficiently identify optimal segmentation points. By focusing on points with significant deviations from the rolling mean and standard deviation, CaT maintains the accuracy of the traditional Top-Down approach while significantly reducing computational time. We evaluate CaT across multiple datasets, demonstrating that it achieves approximation errors comparable to Top-Down and consistently outperforms Sliding Window and Bottom-Up methods in both accuracy and efficiency. Our results suggest that CaT is a robust and practical alternative for time series segmentation, offering substantial improvements in computational efficiency without compromising accuracy. This makes CaT particularly suitable for real-time and large-scale applications, where both speed and precision are crucial.