GT-DTW: Bridging Graph Theory and Dynamic Time Warping for Complex Time
Series Analysis
Abstract
Classification of time series data plays a critical role across various
domains, enabling pattern recognition and trend prediction. Traditional
methods like Dynamic Time Warping (DTW) have been widely used to measure
similarity between time series, but there are challenges related to
computational complexity and sensitivity to noise. The conventional DTW
approach, with its quadratic time complexity, can be inefficient for
large datasets, and some implementations may struggle with noise and
local variations. To overcome these limitations, a novel method called
Graph-Theoretic Dynamic Time Warping (GT-DTW) is proposed. GT-DTW
represents each time series as a graph, applies DTW on the graph
representations and calculates the distances between different time
series based on these graph representations. This approach provides a
robust and computationally efficient method for time series
classification, and experimental results show that GT-DTW provides
better results when compared with conventional methods on the benchmark
datasets from the UCR time series database. GT-DTW also demonstrates
enhanced effectiveness in situations where time series share fundamental
similarities, yet are affected by intricate transformations, noise,
inconsistencies in length, and localized distortions.