PaperlayerView exact revision on arXiv

Source-linked AI summary

Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching

Pierre-François Marteau

arXiv:cs/0703033v5cs.IR

TL;DR

Time-series similarity requires elastic matching that tolerates time shifts while retaining metric properties useful for retrieval. The paper introduces TWED as a dynamic-programming edit distance with stiffness adjustment, proves it is a metric, derives a down-sampling lower bound, and finds effective performance in a classification experiment relative to established measures.

  • Problem

    The paper addresses elastic time-series similarity that tolerates time shifting while retaining distance properties, especially the triangle inequality needed for retrieval.

  • Method

    TWED models time-series matching as a minimum-cost sequence of graphical edit operations computed by dynamic programming, with stiffness adjustment and a down-sampling lower bound.

  • Results

    TWED is shown to be a metric and performs significantly better on average than Euclidean distance and DTW, and slightly better than LCSS in the reported experiment.

  • Takeaways & Limitations

    TWED combines time-shift tolerance with metric structure that can support time-series retrieval and comparison across down-sampled and original representations.

Abstract

from arXiv · show

In a way similar to the string-to-string correction problem we address time series similarity in the light of a time-series-to-time-series-correction problem for which the similarity between two time series is measured as the minimum cost sequence of "edit operations" needed to transform one time series into another. To define the "edit operations" we use the paradigm of a graphical editing process and end up with a dynamic programming algorithm that we call Time Warp Edit Distance (TWED). TWED is slightly different in form from Dynamic Time Warping, Longest Common Subsequence or Edit Distance with Real Penalty algorithms. In particular, it highlights a parameter which drives a kind of stiffness of the elastic measure along the time axis. We show that the similarity provided by TWED is a metric potentially useful in time series retrieval applications since it could benefit from the triangular inequality property to speed up the retrieval process while tuning the parameters of the elastic measure. In that context, a lower bound is derived to relate the matching of time series into down sampled representation spaces to the matching into the original space. Empiric quality of the TWED distance is evaluated on a simple classification task. Compared to Edit Distance, Dynamic Time Warping, Longest Common Subsequnce and Edit Distance with Real Penalty, TWED has proven to be quite effective on the considered experimental task.

P.F. MARTEAU

The paper proposes TWED, an elastic time-series distance that combines time shifting with metric properties, including the triangle inequality. It introduces stiffness control, a down-sampling lower bound, and an empirical comparison with established measures.

  • TWED is proposed as a new elastic metric for time-series matching that jointly supports time shifting and the triangle inequality.
  • A stiffness parameter controls TWED’s elasticity, placing it between Euclidean distance and DTW.
  • Time-stamp differences between matched samples contribute to local matching costs, allowing the measure to account for temporal spacing.
  • A lower bound links matching in down-sampled representations to matching in the original space, supporting pruning during retrieval.
  • A simple classification experiment evaluates TWED against Euclidean Distance, DTW, LCSS, and ERP, while also analyzing stiffness effects on classification error.

II. MOTIVATION FOR A SIMILARITY MEASURE THAT VERIFIES THE TRIANGLE INEQUALITY AND TAKES TIMESTAMP DIFFERENCES INTO ACCOUNT

The motivation is to compare time series with temporal misalignment while preserving metric structure and timestamp information. This supports retrieval and comparison of nonuniformly sampled or down-sampled data.

  • Threshold-based limits on index differences may reduce effectiveness, motivating a linear penalty for temporal separation.
  • Using timestamps instead of sample indices can handle varying sampling rates without resampling the data.
  • Nonuniform sampling makes sample timing important, because ignoring occurrence times can damage phase, frequency, and spike-slope information.
  • A metric lower bound can relate down-sampled and original-space distances and enable pruning in the down-sampled space.

III. ELASTIC SIMILARITY IN LIGHT OF THE SYMBOLIC EDIT DISTANCE

The paper frames time-series matching as an edit-distance problem, extending symbolic edit operations to time-series samples. It positions TWED among elastic measures such as DTW, ERP, LCSS, and PPM.

  • Symbolic edit distance transforms one sequence into another through insertions, deletions, and substitutions, with dynamic programming computing minimum cost.
  • TWED develops this framework into an elastic metric for time-series matching.
  • The time-series formulation defines edit operations as matches, deletions, or insertions between samples, including a null sample.
  • A general cost function assigns nonnegative costs to edit operations and defines the similarity recursively over finite time series.
  • DTW, ERP, PPM, and LCSS are presented as special cases or related developments within the edit-distance framework.

B. The DTW special case

DTW omits time-stamp values from edit-operation costs, using only spatial sample vectors. This restriction means DTW does not satisfy the triangle inequality.

  • DTW formulation: DTW defines similarity by minimizing cumulative spatial distances between matched samples.The distance uses an Lp norm between sample vectors and does not include time stamps.
  • DTW formulation: DTW edit-operation costs use vectors in S rather than augmented vectors containing time coordinates.The time-stamp values are explicitly excluded from the costs.
  • Metric limitation: DTW does not comply with the triangle inequality.The section identifies this as one of DTW's main restrictions and refers to an example demonstrating it.
  • ERP comparison: ERP likewise excludes time stamps and is therefore a distance on S but not on T × S.Its gap handling additionally uses a constant g in S.
  • ERP comparison: ERP sets g to 0 in some interpretations to preserve the transformed series' mean when gap samples are added.This is presented as an author-reported recommendation for ERP's constant gap value.

B A LCSS

The section reviews LCSS and related sequence-matching models, emphasizing dynamic-programming treatment of matches, insertions, deletions, and gaps. It then introduces TWED as an alternative edit-operation design for time-series alignment.

  • LCSS: LCSS gives a match reward of 1 and no reward to insertion or deletion operations.Its normalized dissimilarity is described as formally close to ERP.
  • Related models: Point-pattern matching uses a metric that measures the minimum space needed to delete or insert points between patterns.For positive increments, this measure coincides with ERP applied to the increment lists.
  • Related models: Bioinformatics sequence models represent substitutions, insertions, and deletions through dynamic programming, with affine penalties for gap sequences.The affine gap penalty depends on gap length, gap opening, and gap extension.
  • TWED: TWED proposes an alternative definition of edit operations for time-series alignment.The approach reuses the string-editing analogy while introducing differences tailored to time series.

A. Graphical Editor Paradigm

TWED models time-series matching as a graphical editing game in which two curves are edited from left to right until they superimpose. Its three operations assign costs based on geometric displacement and deletion penalties.

  • Graphical representation: The graphical editor represents time on the horizontal axis and projected spatial coordinates on the vertical axis.Discrete series are treated as sequences of linear segments between successive samples.
  • Edit operations: TWED replaces classical delete, insert, and match operations with delete-A, delete-B, and match.These operations edit the two series while preserving their left-to-right progression.
  • Edit operations: Deleting a sample costs a term proportional to its displacement from the previous sample plus a constant penalty λ.The same structure is specified for deletions in both time series.
  • Edit operations: Matching two segments costs an amount proportional to the sum of the two cross-series vector lengths.The vectors connect corresponding endpoints across the two time series.
  • Editing constraints: Each edit advances at least one series index, and processed segments cannot be reused in later operations.This constraint yields an ordered sequence of edit operations and index pairs.
  • Dynamic programming: The dynamic-programming solution provides a successful minimum-cost editing sequence for finite discrete time series.The cited result states this minimal global cost property for time series in U2.

C. Some properties of TWED

TWED is established as a metric with adjustable stiffness and standard dynamic-programming complexity. Its temporal penalty distinguishes it from spatial-only elastic measures and supports triangle-inequality-based comparisons.

  • Metric properties: TWED is a distance on the set of finite discrete time series.This is stated as Proposition 1.
  • Metric properties: TWED is nonnegative and equals zero exactly when the two finite discrete time series are identical.The identity condition is stated for γ and λ equal to zero in the displayed proposition.
  • Metric properties: TWED satisfies the triangle inequality: δ(A,B) ≤ δ(A,C) + δ(C,B).The property is stated for any finite discrete time series A, B, and C.
  • Stiffness adjustment: The parameter γ controls stiffness by weighting temporal displacement in the edit costs.The formulation separates spatial and temporal penalties, interpolating conceptually between Euclidean distance and DTW.
  • Stiffness adjustment: γ must be positive for TWED to be a distance on the combined time-and-space domain.When γ = 0, the measure remains a distance on S but not on T × S.
  • Algorithmic complexity: TWED has O(p.q) time and space complexity, with O(p+q) extra space possible through tabulation.The complexities match DTW and ERP before the extra-space optimization.

V. BOUNDING THE TWED MEASURE

The section derives bounds connecting TWED distances computed on original and piecewise-constant down-sampled time series. These bounds support efficient range-query filtering when approximations are sufficiently accurate and parameter terms are small.

  • Piecewise constant approximations with few segments can improve the efficiency of the LP-distance.The approximation may be obtained using heuristic, near-optimal, or optimal solutions.
  • The derived upper bound quantifies the difference between TWED distances in the original and down-sampled spaces.It incorporates approximation distances and terms involving time differences and TWED parameters.
  • The corresponding lower bounds can be tight when the approximations are close to the original series and the relevant parameter terms are comparatively small.The stated conditions concern approximation quality and the quantities involving γ, λ, and the average time difference ΔT.
  • The inequalities can support fast and dirty filters for range queries, including cases where some approximation parameters cannot be made small.Candidates can be rejected when the bound places them outside the query radius.
  • Precomputed approximation distances enable tighter retrieval bounds, while a second bound can be evaluated during retrieval using L1-distances.The approximation-based complexity is described as lower than evaluating the full distance when using a reduced representation.

VI. EXPERIMENTATIONS

The experiments evaluate TWED and optimized TWED against several elastic and edit-based distances using nearest-neighbor classification on original and down-sampled UCR time series. TWED has the lowest average testing error on original series, while time stamps make it comparatively robust after down-sampling.

  • Classification task experiment: The classification task assigns an unknown time series the category of its nearest training-series neighbor.Testing series are distinct from the training set, and the nearest neighbor is selected under each distance or similarity measure.
  • Parameter selection: Parameters for OTWED, ODTW, and LCSS are selected on training data by minimizing leave-one-out classification error before testing.OTWED selects γ and λ; the same training-based procedure sets parameters for ODTW and LCSS.
  • Original time series: TWED exhibits the lowest average testing error against ED, DTW, ODTW, ERP, and LCSS on the original time series.The reported average gains are 2.5% against ODTW, 4.7% against LCSS, 3% against ERP, 9.4% against ED, and 8.8% against DTW.
  • Down-sampled time series: 2x faster error-rate drops for ED, DTW, ERP, LCSS, and ODTW than for TWED are reported on down-sampled time series.The down-sampled experiment uses optimal piecewise-constant approximation with exactly 50% fewer samples.
  • Down-sampled time series: Using time stamps when matching non-uniformly down-sampled series seems quite effective.This conclusion is stated for the experimental setting involving varying sampling rates.

SERIES FOR ED, DTW, ODTW, LCSS, ERP, AND OTWED DISTANCE

The range-query experiment evaluates a multiresolution Fast and Dirty Filter against linear scanning on heterogeneous and homogeneous databases. The filter is much faster for small radii but loses its advantage for larger radii.

  • Range query search experiment: The experiment measures processing time for extracting series within radius R of a randomly selected reference series and compares FDF with Linear Scanning.It uses heterogeneous and homogeneous databases and filters 100 random queries.
  • Filter procedure: The Fast and Dirty Filter iteratively evaluates the bound from coarse to fine resolutions and rejects candidates as soon as the inequality is satisfied.Each successive resolution eliminates half of the samples, with the finest level corresponding to the original series.
  • Results: An order of magnitude faster processing is achieved by FDF than LS for radii from 1 to 4 on both databases.FDF performs well for small radii and matches LS for radius values between 16 and 32.
  • Results: FDF performs worse than LS for greater radii because inequality (13) no longer applies efficiently.The stated limitation concerns the filter's effectiveness as the query radius increases.

VII. CONCLUSION

The paper presents TWED as an elastic time-series similarity measure with metric properties, tunable stiffness, and applications to retrieval and classification. It also develops a lower-bound procedure for down-sampled representations, while noting that a linear-complexity lower bound remains unresolved.

  • TWED is introduced as an elastic similarity measure for matching time series from a graphical curve-editing perspective.
  • TWED is a metric that can complement metric-space search methods for time-series retrieval when time-shift tolerance is needed.
  • The stiffness parameter controls TWED’s elasticity, positioning it between Euclidian distance and DTW.A second parameter imposes a constant penalty for insertions or deletions, and both parameters can be optimized when training data are available.
  • The proposed lower bound links TWED on polygonal or piecewise-constant approximations to TWED on the original series through the triangle inequality.
  • The approximation-space computation cost decreases quadratically with compression rate, and a fast filter based on the lower bound can provide an order-of-magnitude processing-time gain.
  • The proposed lower bound has no linear complexity, and finding an effectively linear lower bound for down-sampled approximations remains open.
  • On 20 datasets using first-near-neighbor classification, TWED performed significantly better on average than Euclidian distance and DTW, and slightly better than LCSS and ERP.For down-sampled series, TWED was reported as more robust than the other tested measures, particularly when sampling was not uniform.

VIII. APPENDIX

The appendix derives inequalities connecting TWED evaluations on original and approximated time series. These bounds use approximation-error terms and the triangle inequality to relate the two matching spaces.

  • The appendix upper-bounds the matching of two original time series using the matching of their approximations in the down-sampled space.
  • The derivation applies the triangle inequality to connect original-series distances, approximation distances, and cross-space matching terms.
  • The displayed inequalities include approximation-specific terms for both time series and their corresponding down-sampled representations.
Loading cs/0703033v5…