Source-linked AI summary
Experimental Comparison of Representation Methods and Distance Measures for Time Series Data
Xiaoyue Wang, Hui Ding, Goce Trajcevski, Peter Scheuermann, Eamonn Keogh
TL;DR
Time-series research lacks broad, consistent evidence for comparing numerous representations and similarity measures, despite conflicting claims from narrowly focused studies. The paper addresses this gap by re-implementing and evaluating 8 representation methods and 9 similarity measures across 38 diverse data sets. It finds broad patterns across classification and indexing experiments, while cautioning that some conclusions depend on data-set characteristics and that literature claims may be overly optimistic.
Problem
Conflicting and narrowly focused comparisons of time-series representations and similarity measures leave a need for comprehensive validation.
Method
The study re-implements 8 dimension-reduction representations and 9 similarity measures and their variants, evaluating them on 38 diverse time-series data sets.
Results
Across the experiments, representation methods generally show little difference in pruning power, while elastic measures can outperform Euclidean distance on small classification data sets and converge toward it as training size grows.
Takeaways & Limitations
The study provides a consolidation intended to support references and benchmarks, while indicating that some claims in the literature may be unduly optimistic.
Takeaways & Limitations
The usefulness of TQuEST cannot be determined from its experiment alone because favorable performance depends on characteristics of the data set.
Abstract
from arXiv · showhide
The previous decade has brought a remarkable increase of the interest in applications that deal with querying and mining of time series data. Many of the research efforts in this context have focused on introducing new representation methods for dimensionality reduction or novel similarity measures for the underlying data. In the vast majority of cases, each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive experimental study re-implementing eight different time series representations and nine similarity measures and their variants, and testing their effectiveness on thirty-eight time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. In addition to providing a unified validation of some of the existing achievements, our experiments also indicate that, in some cases, certain claims in the literature may be unduly optimistic.
1 Introduction
Time-series research has produced many competing representations and similarity measures, but narrow and conflicting comparisons motivate a comprehensive evaluation. This study re-implements and compares these techniques across diverse data sets to establish broader empirical evidence.
- Motivation: Time-series data are increasingly generated across application domains, driving interest in querying and mining them.Examples include financial, scientific, medical, biological, sensor-network, and location-based data.
- Motivation: Raw time series are high-dimensional, making direct processing and storage expensive and motivating dimensionality-reduction representations.Representations should reduce dimensionality while preserving fundamental characteristics of the data.
- Research gap: Existing studies introduced many representations and distance measures, often comparing a proposed technique with only selected prior methods.Examples of representations include DFT, SVD, DCT, DWT, PAA, APCA, CHEB, SAX, and IPLA.
- Research gap: Conflicting claims about whether wavelets, DFT, or comparable techniques perform best show the need for comprehensive, benchmark-oriented comparisons.The paper notes that contradictory or inadequate evaluations can confuse practitioners and waste research effort.
- Study contributions: The study re-implements 8 representation methods and 9 similarity measures, compares their pruning power and effectiveness on 38 diverse real-world data sets, and reports analyses from the experiments.The source code and data sets are publicly available.
2 Preliminaries
This section defines time-series representations and similarity measures, then organizes them by how they compress data and align points. It also motivates the study of lower bounding, lock-step, elastic, and editing approaches.
- Time-series preliminaries: A time series is a time-ordered sequence of d-dimensional data points, potentially affected by differing sampling rates, noise, or missing observations.The paper assumes discrete time and defines the series length as the number of data points.
- Representation methods: Representation methods reduce dimensionality to lower processing and storage costs while preserving fundamental characteristics needed for similarity search and mining.The paper distinguishes data-adaptive methods, which minimize global reconstruction error, from non-data-adaptive methods, which use local data properties.
- Representation methods: APCA uses variable-length constant segments with minimal individual reconstruction errors, whereas PAA divides a series into equal-length segments and records their means.These examples illustrate the distinction between adaptive and non-adaptive representations.
- Representation methods: Lower-bounding representations support indexing by guaranteeing that compressed-data distances do not exceed raw-data distances, preventing false negatives.The property applies to the representations marked with an asterisk in Figure 1.
- Similarity measures: Similarity measures include lock-step methods with fixed one-to-one alignment, elastic methods allowing one-to-many matching, and editing methods additionally allowing unmatched points.The paper reviews nine similarity measures and their variants, including Euclidean distance, DTW, LCSS, EDR, ERP, and Swale.
- Similarity measures: Euclidean and related Lp norms are linear, parameter-free, and indexable, but fixed point mappings make them sensitive to noise, temporal misalignment, and local time shifts.DTW instead allows time series to be stretched or compressed, while constrained warping can improve efficiency and accuracy.
3 Comparison of Time Series Representations
The study compares eight time-series representations using lower-bound tightness (TLB), an implementation-independent measure linked to indexing performance. Across experiments, representations generally differ little in pruning power, though periodic data can slightly favor spectral methods and some literature claims appear overly optimistic.
- Representations: All eight studied representations support lower bounding and can index Euclidean distance, DTW, and at least some other elastic measures.Lower bounding guarantees that distances computed on compressed representations do not exceed the corresponding raw-data distances.
- Evaluation measure: TLB is used instead of wall-clock time because it is implementation-independent, reproducible, and predictive of indexing performance.Its value measures lower-bound tightness relative to the true Euclidean distance.
- Evaluation measure: TLB’s relationship with disk-access speedup is nonlinear: doubling a lower bound can produce substantially more than a twofold reduction in disk accesses.A TLB of zero implies retrieving every series, whereas a TLB of one can reduce retrieval to a single object after in-memory processing.
- Experimental findings: The results indicate that some earlier claims of large representation differences may reflect experimental errors or bias.One cited example concerns failing to exploit DFT’s complex-conjugate property.
- Experimental findings: Highly periodic data can slightly favor spectral representations such as DCT, DFT, and CHEB over polynomial representations.The comparison identifies this as a data-dependent pattern rather than a universal ranking.
- Experimental findings: The most extreme differences found across more than 80 diverse data sets suggest little general separation among representations in pruning power.The ECG experiment varied series lengths, coefficient counts, and representation parameters through repeated random sampling.
4 Comparison of Time Series Similarity Measures
The experiments compare similarity measures across data-set sizes, accuracy, speed, and parameter settings. Results show that no measure is uniformly superior, while some literature claims depend strongly on data-set scale and experimental choices.
- 4.1 The Effect of Data Set Size on Accuracy and Speed: For elastic measures, accuracy and amortized speed depend critically on data-set size.As data sets grow, elastic-measure speed approaches lock-step measures, while lock-step accuracy approaches elastic measures.
- 4.1 The Effect of Data Set Size on Accuracy and Speed: 400 training series eliminate the statistically significant accuracy gap between DTW and Euclidean distance on CBF; Two-Patterns requires a few thousand.DTW is significantly more accurate on small data sets, but Euclidean accuracy converges toward DTW as training sets grow.
- 4.1 The Effect of Data Set Size on Accuracy and Speed: At 6400 objects, the DTW pruning fraction reaches P = 0.9696, making about 97% of objects processable at Euclidean-distance cost.The reported timing uses sequential search with a lower bound and no indexing.
- 4.3 Analysis of Classification Accuracy: Constrained DTW matches or slightly exceeds full DTW accuracy while reducing computation time and enabling lower-bounding techniques.Full DTW outperforms Euclidean distance on the tested data sets.
- 4.3 Analysis of Classification Accuracy: LCSS, EDR, and ERP outperform Euclidean distance, but the experiments provide no clear evidence that any similarity measure is universally most accurate.Measures that perform well on some data sets are often inferior on others, and edit-distance measures need not outperform DTW.
- 4.3 Analysis of Classification Accuracy: SpADe is generally close to Euclidean accuracy and inferior to DTW, while TQuEST is worse than both on most tested data sets.SpADe has many parameters and small tuning sets, making parameter selection difficult; the results do not determine its overall usefulness.
5 Exploding the Myths of Surrounding Dynamic Time Warping
The paper challenges optimistic claims about DTW speedups and alternative distance measures by reexamining published evidence under reproducible, fair experimental conditions. It finds that many reported advantages are much smaller than claimed, while parameter tuning and test-data feedback can create misleading impressions of superiority.
- DTW speed myths: 0.011 seconds was the reproduced lower-bound scan time, 727 times faster than the published claim and faster than the claimed improvement.The comparison used identical parameters to the earlier stock-market experiment.
- DTW speed myths: 0.016 seconds was the reproduced DTW time on the ECG task, 34,506 times faster than the published 552.1-second result.The reproduction used identical conditions to the earlier comparison.
- Lower-bound limits: 1.37 times faster was the maximum improvement the experiments indicated could be obtained even with an idealized optimal lower bound.The paper contrasts this limit with literature claims of 10×, 25×, and up to 222× improvements.
- Lower-bound limits: 1.0–1.3 was the speedup range obtained on more general data sets from tighter lower bounds, contradicting claims of much larger improvements.Across data sets and settings, the same basic pattern persisted; one cited study reported a mean speedup of about 1.4.
- Lower-bound limits: Tighter lower bounds cannot significantly speed DTW search because their construction overhead may exceed the cost of computing the original DTW distance.The paper concludes that speedups remain possible through other means, but not significantly through tighter lower bounds alone.
- Accuracy claims and experimental fairness: 17 of 20 problems were lost to constrained DTW in a fair blind test, while the three wins over it were only 2.0%, 0.4%, and 0.1%.The datasets largely overlapped with those in the UCR archive, despite minor changes to train/test splits.
6 Conclusion & Future Work
The study consolidates extensive evaluations of time-series representations and similarity measures, while identifying practical findings, unresolved questions, and planned extensions.
- 8 representation methods and 9 similarity measures, including variants, were evaluated on 38 diverse time-series data sets.
- Elastic measures can be more accurate than Euclidean distance on small classification data sets, while their accuracy converges toward Euclidean distance as training sets grow.
- Constraining warping windows can reduce computation cost and enable effective lower-bounding while preserving or improving accuracy.
- Testing many measures on one train/test split can produce chance improvements that fail to generalize, making overfitting a serious concern.
- The study’s pairwise observations about data-set properties influencing which distance measures work best are explicitly presented as inconclusive.
- The authors plan more rigorous statistical analysis, evaluations with missing points and noise, and validation of similarity-search acceleration.
Above the line Euclidean outperforms L1 norm
The supplied comparisons report which methods outperform others in accuracy, with Euclidean distance and full DTW each winning against several alternatives.
- Euclidean outperforms DISSIM in the supplied comparison.
- DISSIM and TQuEST each outperform full DTW in the supplied comparisons.
- Constrained DTW outperforms full DTW in the supplied comparison.
- Euclidean outperforms ERP, full LCSS, Swale, SpADe, TQuEST, EDR, constrained DTW, and full DTW in the supplied comparisons.
- Full DTW outperforms ERP, full LCSS, Swale, SpADe, and EDR in the supplied comparisons.