TL;DR
This paper presents a large-scale, empirical comparison of 8 time series data representations and 9 similarity measures. The authors found that many claims of superiority for novel methods are often overstated, and that simpler, established techniques like Euclidean distance and Dynamic Time Warping (DTW) remain highly competitive, especially with sufficient data.
What Problem Does This Paper Address?
The field of time series data mining has exploded with new methods for representing time series (to reduce dimensionality) and measuring their similarity. While individual papers often claim their proposed method is superior, these claims are typically based on narrowly focused experiments. This leads to a confusing landscape where practitioners struggle to choose the best tools, and researchers may waste effort on incremental improvements over methods whose true performance is not well understood. The authors aim to provide a unified, comprehensive validation of existing state-of-the-art techniques to clarify their actual effectiveness and identify potential overstatements in the literature.
Methods
The core of this work is a large-scale experimental comparison. The authors re-implemented:
- 8 Representation Methods: These techniques aim to reduce the dimensionality of time series data while preserving essential characteristics. The methods include Discrete Fourier Transformation (DFT), Discrete Cosine Transformation (DCT), Discrete Wavelet Transformation (DWT), Piecewise Aggregate Approximation (PAA), Adaptive Piecewise Constant Approximation (APCA), Symbolic Aggregate Approximation (SAX), Chebyshev Polynomials (CHEB), and Indexable Piecewise Linear Approximation (IPLA). A key property investigated is "lower bounding," which allows for efficient indexing by guaranteeing that the distance between representations is less than or equal to the true distance.
- 9 Similarity Measures: These algorithms quantify how alike two time series are. They are categorized into "lock-step" measures (where points are compared directly based on their index, e.g., Euclidean distance) and "elastic" measures (which allow for time warping, e.g., Dynamic Time Warping). The measures include Lp-norms (L1, L2, L∞), DISSIM, Dynamic Time Warping (DTW), Longest Common Subsequence (LCSS), Edit Distance with Real Penalty (ERP), Edit Distance on Real sequence (EDR), Symbolic Aggregate Approximation (SAX), and Threshold Queries (TQUEST), and Spatial Assembling Distance (SpADe).
The evaluation focused on two main aspects: the "tightness of lower bounds" for representations (indicating their effectiveness for indexing) and the "classification accuracy" for similarity measures using a 1-Nearest Neighbor (1NN) classifier.
Datasets
The experiments utilized 38 diverse, real-world time series datasets from the UCR Time Series Data Mining Archive. These datasets are publicly available and represent a broad spectrum of application domains. The authors note that this collection represents a significant portion of publicly available, labeled time series data. For some experiments, synthetic datasets (Two-Patterns and CBF) were generated to study the effect of data set size.
Key Insights and Ideas
- Overstated Claims: Many claims of superiority for novel representation methods and similarity measures are not supported by extensive, fair comparisons. The authors found that simpler, older methods often perform comparably or even better.
- The Power of Data Size: The performance gap between "elastic" (e.g., DTW) and "lock-step" (e.g., Euclidean) similarity measures diminishes significantly as the size of the training dataset increases. For large datasets, lock-step measures become almost as accurate as elastic ones.
- Lower Bounding is Key for Indexing: Representations that allow for lower bounding are crucial for efficient indexing of time series databases. The tightness of these lower bounds directly impacts pruning power.
- Constrained DTW is Effective: Constraining the warping window size in DTW (and LCSS) can significantly reduce computation time without sacrificing accuracy, and can even improve it.
- Edit Distances vs. DTW: While edit distance-based measures (LCSS, EDR, ERP) are often touted as superior to DTW, the authors found their performance to be very close to DTW, with EDR showing a slight potential advantage.
- Novelty Doesn't Always Mean Superiority: Newer measures like TQUEST and SpADe generally performed worse than established elastic measures.
- "Arbitrarily Naive Algorithm" (ANA): The appendix humorously illustrates how seemingly novel algorithms can be constructed by arbitrarily tuning parameters (like using monkey DNA to weight Euclidean distance), highlighting the importance of rigorous, reproducible evaluation.
Key Results
- Representations: For most datasets, the "tightness of lower bounds" (a proxy for indexing effectiveness) showed very little difference between the tested representation methods. While spectral methods (DCT, DFT, CHEB) had a slight edge on highly periodic data, and APCA on bursty data, the differences were generally minor across the 38 datasets.
- Similarity Measures:
- Lp-norms: L1 and L2 (Euclidean) norms performed similarly and significantly outperformed the L∞-norm.
- DTW: Full DTW consistently outperformed Euclidean distance. Constrained DTW performed similarly or slightly better than full DTW, offering a more efficient alternative.
- Edit Distances (LCSS, EDR, ERP): These measures generally outperformed Euclidean distance but were very close in accuracy to DTW. EDR showed a slight edge over DTW in some cases.
- DISSIM: Performed slightly better than Euclidean but was inferior to DTW.
- TQUEST & SpADe: Generally performed worse than established elastic measures.
- Data Size Impact: On small datasets, elastic measures like DTW were significantly more accurate than Euclidean. However, as dataset size grew, the accuracy difference converged, and the speed advantage of lock-step measures became more pronounced. For example, with 6400 training instances, the amortized speed of DTW approached that of Euclidean distance.
Limitations and Future Work
- Parameter Tuning: The authors acknowledge that some measures (like SpADe) have many parameters, making it difficult to find optimal settings, especially with limited tuning data.
- Future Work:
- Conduct more rigorous statistical analysis of the experimental results.
- Extend evaluations to include missing points and noisy data.
- Validate the effectiveness of techniques for expediting similarity search.
- Investigate if specific data characteristics (e.g., periodicity, burstiness) critically impact the choice of distance measure, potentially leading to more targeted algorithm selection.
Summary updated