Abstract
Dynamic time warping (DTW) is a cornerstone dissimilarity measure in time series analysis, yet it remains vulnerable to noise and outliers, which often lead to the "singularity problem" and measurement bias. Furthermore, its $O(N^2)$ time complexity limits its utility in real-time or large-scale applications. This paper introduces RobustDTW, a novel measure designed to mitigate the impact of noise through a joint optimization of trend estimation and time warping. By utilizing a temporal graph trend filtering approach within a multi-level framework, RobustDTW achieves both robustness and near-linear efficiency. Experimental results on real-world cloud monitoring and periodicity datasets demonstrate that RobustDTW significantly outperforms existing DTW variants in outlier detection and periodicity identification.
Introduction
In time series analysis, finding the optimal alignment between two sequences is critical for tasks ranging from speech recognition to financial forecasting. Dynamic Time Warping (DTW) has long been the standard for this task due to its ability to handle sequences that vary in speed or phase. However, DTW suffers from two primary limitations that hinder its performance in production environments:
- The Singularity Problem: Standard DTW is highly sensitive to outliers. A single random spike in one series can cause the algorithm to map multiple points of the other series to that single outlier, creating a "singularity" that distorts the distance metric.
- Computational Complexity: The quadratic time complexity of the standard DTW algorithm makes it computationally prohibitive for long sequences or high-frequency streaming data.
While existing modifications like FastDTW address speed, and others attempt to handle noise, few provide a unified solution that addresses both robustness and efficiency simultaneously. RobustDTW fills this gap by treating alignment and noise reduction as a coupled optimization problem.
Methodology
Joint Optimization and Alternating Estimation
The core philosophy of RobustDTW is that data cleaning and alignment should not be treated as sequential, independent steps. Instead, the algorithm employs an alternating optimization strategy. It iteratively alternates between two phases:
- Trend Estimation: Fixing the current alignment to estimate the underlying "true" signal (trend) of the series.
- Alignment Refinement: Fixing the estimated trend to optimize the time warp function.
This approach ensures that the alignment is based on the structural signal rather than transient noise.
Temporal Graph Trend Filtering
To perform the trend estimation, the authors propose Temporal Graph Trend Filtering. A graph is constructed where nodes represent time points from both series. Edges are established between immediate temporal neighbors within a series and between "peer" points in the other series as determined by the current alignment. By applying $L_1$ penalization to the differences across this graph, the model effectively smooths out "spiky" noise while preserving the essential shape of the signal. This graph-based regularization leverages information from both sequences to inform the denoising of each.
Multi-level Framework
To overcome the $O(N^2)$ bottleneck, RobustDTW utilizes a coarse-to-fine multi-level framework. The algorithm first downsamples the time series to a lower resolution to find a rough alignment and trend. It then repeatedly upsamples and refines these estimates at progressively higher resolutions. This hierarchical approach constrains the search space for the warping path, resulting in near-linear complexity and significantly faster execution times compared to standard DTW.
Experimental Evaluation
Outlier Detection
The effectiveness of RobustDTW was tested on real-world cloud monitoring datasets, including API Response Time (RT) and Network Speed (NetSpd). When integrated with the Local Outlier Factor (LOF) algorithm, RobustDTW demonstrated superior resilience to noise. In the NetSpd dataset, which contained various spikes and dips, RobustDTW maintained an AUC of 0.938, whereas standard DTW fell to 0.627. This highlights the algorithm's ability to ignore non-representative fluctuations that typically mislead traditional measures.
Periodicity Detection
The authors extended RobustDTW to periodicity detection by implementing a slicing algorithm that compares segments of a series. On a benchmark of 200 service monitoring series characterized by non-stationarity and complex patterns, RobustDTW achieved an F1 score of 0.966. This outperformed specialized state-of-the-art methods such as RobustPeriod (0.911) and AUTOPERIOD (0.827).
Efficiency
Benchmark tests on synthetic datasets (lengths $2^6$ to $2^{13}$) confirmed that RobustDTW scales efficiently. While the iterative nature of the optimization adds a constant overhead compared to FastDTW, it remains orders of magnitude faster than standard DTW, making it suitable for large-scale industrial applications.
Conclusion
RobustDTW represents a significant advancement in time series dissimilarity measures. By integrating temporal graph trend filtering into a multi-level alignment framework, it successfully addresses the dual challenges of noise sensitivity and computational cost. While future work may further explore hyperparameter automation for the $L_1$ regularization and extensions into high-dimensional multivariate data, RobustDTW currently stands as a robust and scalable solution for modern anomaly and periodicity detection tasks.
Summary updated