Source-linked AI summary
Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound
Daniel Lemire
TL;DR
DTW is useful for comparing time series but lacks the triangle inequality and can be expensive to compute, motivating lower-bound pruning. The paper introduces a two-pass search that applies LB Keogh followed by LB Improved, and reports retrieval speedups of three times or more in several time-series databases. The approach is less effective on synthetic data sets where both bounds prune too few candidates.
Problem
DTW lacks the triangle inequality and typically requires quadratic-time computation, creating a need for efficient lower bounds during nearest-neighbor search.
Method
The method applies LB Keogh first and then computes the tighter LB Improved bound before evaluating full DTW for surviving candidates.
Results
The two-pass pruning technique improves retrieval speed by three times or more in several time-series databases.
Takeaways & Limitations
LB Improved’s added pruning power can outweigh its slightly higher computation cost, making overall retrieval several times faster.
Takeaways & Limitations
On some synthetic data sets, neither LB Keogh nor LB Improved prunes enough candidates, making the algorithms comparable in speed.
Abstract
from arXiv · showhide
The Dynamic Time Warping (DTW) is a popular similarity measure between time series. The DTW fails to satisfy the triangle inequality and its computation requires quadratic time. Hence, to find closest neighbors quickly, we use bounding techniques. We can avoid most DTW computations with an inexpensive lower bound (LB Keogh). We compare LB Keogh with a tighter lower bound (LB Improved). We find that LB Improved-based search is faster. As an example, our approach is 2-3 times faster over random-walk and shape time series.
1 Introduction
DTW aligns time series flexibly but lacks metric properties and can require quadratic computation, motivating inexpensive lower bounds for nearest-neighbor search. The paper develops a two-pass approach that first uses LB Keogh and then a tighter bound, and reports substantially faster retrieval.
- DTW optimally aligns data points from two time series rather than comparing only corresponding positions.
- DTW lacks the triangle inequality, so conventional metric indexing methods do not directly apply.
- The two-pass method computes LB Keogh first, then a tighter lower bound before resorting to full DTW.
- The DTW distance decreases monotonically as the locality constraint w increases, with w = 0 yielding the l_p distance.
- Typical monotonic DTW computation requires O(n^2) time when the locality window is w = n/10.
- For value-separated series, DTW1 equals the l1 norm.
5 Computing Lower Bounds on the DTW
The paper derives generic lower bounds for DTW using intermediate time series constrained by the warping envelope. These bounds also characterize approximation error and support both LB Keogh and the tighter LB Improved bound.
- A warping-envelope-constrained intermediate series h yields a lower bound on DTW and NDTW.
- The generic theorem implies the original LB Keogh lower bound and provides a lower bound on its error, enabling LB Improved.
- The approximation error of ||x-h||p is bounded by ||h-y||p for both DTWp(x,y) and NDTWp(x,y).
- For value-separated series, the approximation error is exactly ||h-y||1.
6 Warping Envelopes
The warping envelope can be computed efficiently rather than by repeatedly scanning each locality window.
- A naive warping-envelope computation takes O(nw) time, whereas the proposed method uses at most 3n comparisons.
7 LB Keogh
LB Keogh projects a candidate series onto the query’s warping envelope and measures the resulting distance as a DTW lower bound. This inexpensive bound can prune candidates before full DTW computation.
- The projection H(x,y) of x onto y lies within y’s warping envelope.
- LB Keogh_p(x,y) is defined as ||x-H(x,y)||p and lower-bounds both NDTWp(x,y) and DTWp(x,y).
- Nearest-neighbor search computes LB Keogh for each candidate and skips full DTW when the bound is sufficiently large.
8 LB Improved
LB Improved tightens LB Keogh by adding a second lower-bound computation based on the projection of x onto y’s envelope. Applied as a two-pass search, it prunes candidates before resorting to full DTW.
- LB Improved1(x, y) combines LB Keogh1(x, y) with a second LB Keogh term computed between y and the envelope of x’s projection.The first term measures distance from x to y’s envelope; the second measures distance from y to the envelope of the projected x.
- LB Improved is a lower bound to DTW, satisfying DTWp(x, y) ≥ NDTWp(x, y) ≥ LB Improvedp(x, y).
- The two-pass algorithm first applies LB Keogh1, then adds the second term only for candidates that survive the first pruning test.Candidates surviving both lower-bound tests undergo full DTW computation.
- At most (2N + 3)n + 5(1 − α)Nn comparisons are required for a database of N time series when α is the fraction pruned by LB Keogh.
9 Using a multidimensional indexing structure
The multidimensional indexing approach projects time series and envelopes into a lower-dimensional space for R*-tree search. Adding LB Keogh and then LB Improved increases pruning before full DTW evaluation.
- Time series and their envelopes are projected into a d-dimensional space using piecewise sums for multidimensional indexing.The projection uses a disjoint cover of the time-series indexes, with experiment-specific intervals defined for the cover.
- The LB Improved computation compares x with y’s envelope, projects x onto that envelope, computes the projection’s envelope, and adds the resulting difference.
- The Zhu-Shasha R*-tree retrieves candidates near the projected query envelope and updates the best DTW distance as candidates are examined.
- Dimensionality reduction preserves a lower bound to DTW1, but it weakens LB Keogh’s pruning power because d(E, Pd(x)) ≤ LB Keogh1(x, y).
- R*-tree+LB Keogh filters candidates with LB Keogh before full DTW, while R*-tree+LB Improved adds the second lower-bound test first.The paper identifies R*-tree+LB Improved as having maximal pruning power among the three alternatives.
10 Comparing Zhu-Shasha R*-tree, LB Keogh, and LB Improved
The benchmarks compare Zhu-Shasha R*-tree, R*-tree with LB Keogh, and R*-tree with LB Improved for DTW nearest-neighbor retrieval. LB Improved generally prunes more candidates and accelerates retrieval, especially on random-walk and shape data, while gains are limited on simple series and smaller locality constraints.
- Implementation and benchmarking: Early abandoning changes retrieval time by less than ≈1% for both LB Keogh and LB Improved.The authors attribute the small difference partly to candidates from the Zhu-Shasha R*-tree rarely being poor enough for efficient early abandoning.
- Synthetic data sets: LB Improved prunes between 2 and 4 times more candidates than LB Keogh, while R*-tree+LB Improved is faster than Zhu-Shasha R*-tree by a factor between 0 and 6.
- Synthetic data sets: Simple Cylinder-Bell-Funnel and Control Charts series yield almost no performance gain over Zhu-Shasha R*-tree because full DTW dominates when pruning is modest.LB Improved prunes 40% and 15% of candidates, respectively, on these data sets.
- Shape data sets: Shape experiments show LB Improved has twice LB Keogh's pruning power, is twice as fast as R*-tree+LB Keogh, and is over 3 times faster than Zhu-Shasha R*-tree.The experiments use 5,844 1,024-sample heterogeneous-shape series and 15,000 251-sample arrow-head series.
- Locality constraint: Larger locality constraints make retrieval harder and reduce every method's pruning power, but R*-tree+LB Improved remains at least as fast as Zhu-Shasha R*-tree for w ∈ {5%, 10%, 20%}.Even with smaller locality constraints, R*-tree+LB Improved can still be three times faster than Zhu-Shasha R*-tree.
11 Conclusion
The paper concludes that two-pass pruning can substantially accelerate DTW retrieval, although insufficient pruning on some synthetic data sets leaves methods comparable in speed.
- Two-pass pruning improves retrieval speed by three times or more in several time-series databases.LB Improved requires slightly more computation than LB Keogh, but its added pruning power makes overall computation several times faster.
- On some synthetic data sets, neither LB Keogh nor LB Improved prunes enough candidates to outperform the other algorithms in speed.
A Some Properties of Dynamic Time Warping
This section characterizes DTW through warping-path properties, locality constraints, and relationships to ℓ_p distances. It establishes bounds on path length and shows when DTW reduces to an ℓ_p norm.
- A minimal warping path has length at most 2n − 2 for two time series of length n > 1.The bound follows from the fact that each aligned point is either singly aligned on one side or can be removed from the path.
- When one time series is constant, DTW_p and NDTW_p equal the ℓ_p distance between the series for any 0 < p ≤ ∞.
- For p = ∞, if one series is a constant translation of the other, DTW_∞ and NDTW_∞ equal the ℓ_∞ distance.The same result does not hold for finite p.
- For 1 ≤ p < q ≤ ∞, DTW_p is bounded above by (2n − 2)^(1/p−1/q) DTW_q, and the result also holds for non-monotonic DTW.
B The Triangle Inequality
DTW is reflexive and symmetric but generally lacks transitivity and the traditional triangle inequality. The paper derives a locality-dependent weak triangle inequality, with DTW_∞ as an important exception.
- DTW is reflexive and symmetric, but it is not transitive.
- For 1 ≤ p < ∞ and w > 0, no triangle-inequality constant independent of series length and locality constraint exists for DTW_p or NDTW_p.
- Random-walk triples violated the triangle inequality in 20% of cases for DTW1 and 15% for DTW2, while white-noise and Cylinder-Bell-Funnel triples showed no violations.The experiment generated 100,000 triples for each series type.
- For same-length series, DTW_p(x,y) + DTW_p(y,z) ≥ DTW_p(x,z) min(2w + 1, n)^(1/p), including non-monotonic DTW.The constant min(2w + 1, n)^(1/p) is tight.
- DTW_∞ and NDTW_∞ satisfy the traditional triangle inequality.DTW_∞ is therefore a pseudometric, and without locality constraints it is equivalent to the discrete Fréchet distance.
C Which is the Best Distance Measure?
The section compares DTW variants and finds that DTW1 generally provides the strongest nearest-neighbor classification accuracy, with DTW2 usually close behind. DTW∞ is competitive only with very small class sizes, while DTW4 generally performs worse.
- The evaluation uses four synthetic data sets with varying series lengths, class counts, and numbers of instances per class.Average accuracies were computed over 25,000 classification tests across 50 databases, using the reported experimental setup.
- DTW∞ is competitive only when each class has one or two instances; adding more instances does not improve its accuracy.
- For Waveform, DTW1 and DTW2 have comparable classification accuracies, whereas DTW1 outperforms DTW2 on the other three data sets.
- DTW4 has almost always lower classification accuracy than DTW1 or DTW2.
- DTW1 is generally the best choice for time-series classification, while DTW2 is a close second.