Source-linked AI summary
SparseDTW: A Novel Approach to Speed up Dynamic Time Warping
Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri
TL;DR
Standard DTW can require O(mn) space for long sequences. SparseDTW dynamically exploits similarity and correlation to represent the warping matrix sparsely while preserving the optimal path. Experiments report that SparseDTW outperforms DTW, BandDTW, and DC.
Problem
Standard DTW has O(mn) space complexity, which limits its practicality for long sequences; an example with length 28,800 requires at least 800 million matrix entries.
Method
SparseDTW dynamically exploits similarity and correlation between two time series and represents the warping matrix with sparse matrices.
Results
SparseDTW always outperforms DTW, BandDTW, and DC in experiments using synthetic and real-life datasets.
Takeaways & Limitations
SparseDTW finds the optimal warping path efficiently and accurately while exploiting correlation between time series.
Takeaways & Limitations
The divide-and-conquer comparison can fail to recover the optimal path, with the reported final DTW distance differing from standard DTW.
Abstract
from arXiv · showhide
We present a new space-efficient approach, (SparseDTW), to compute the Dynamic Time Warping (DTW) distance between two time series that always yields the optimal result. This is in contrast to other known approaches which typically sacrifice optimality to attain space efficiency. The main idea behind our approach is to dynamically exploit the existence of similarity and/or correlation between the time series. The more the similarity between the time series the less space required to compute the DTW between them. To the best of our knowledge, all other techniques to speedup DTW, impose apriori constraints and do not exploit similarity characteristics that may be present in the data. We conduct experiments and demonstrate that SparseDTW outperforms previous approaches.
1 School of Computer Science and Engineering The University of New South Wales
The section identifies the authors’ institutional affiliation and lists the paper’s subject areas.
- The authors are affiliated with the School of Information Technologies at the University of Sydney, Australia.
- The affiliation includes the email addresses chawla and javidt at the University of Sydney domain.
- The listed keywords are time series, similarity measures, dynamic time warping, and data mining.
1 Introduction
The introduction motivates SparseDTW by the O(mn) space cost of standard DTW and presents a data-adaptive approach intended to reduce space while preserving optimality.
- Standard DTW requires O(mn) space, making long time-series comparisons impractical; 28,800-point stock series would require at least 800 million matrix entries.
- SparseDTW dynamically exploits inherent similarity and correlation between the two time series being compared.
- Its dynamically evolving bands are generally smaller than traditional bands, improving average space complexity through sparse matrix representation.
- SparseDTW always yields the optimal warping path because it does not impose data-independent apriori constraints.
- Because it preserves optimal alignment, SparseDTW can be combined with lower-bound approaches.
2 Related Work
Prior DTW acceleration methods reduce search or computation through constraints, approximation, indexing, or lower bounds; SparseDTW instead uses correlation with a sparse warping matrix.
- DTW is widely used for time-series similarity in ECGs, speech processing, and robotics, but it is a measure rather than a metric.
- Divide and conquer reduces space to linear complexity while retaining quadratic time, but it does not guarantee the optimal DTW distance.
- Sakoe–Chiba constraints reduce the search space by restricting paths near the diagonal, but optimality is lost when the path crosses the band.
- Lower bounds and indexing reduce the number of DTW computations but do not reduce the space complexity of an individual DTW computation.
- FastDTW approximates DTW through multiresolution refinement and depends on a radius constraint, so it does not guarantee the optimal path.
- SparseDTW uses point correlation to store the warping matrix sparsely, an approach the authors say had not previously been used to reduce required space.
3 Dynamic Time Warping (DTW)
DTW computes similarity between time series by filling distance and warping matrices, then selecting a minimum-cost path that obeys monotonicity, continuity, and boundary constraints.
- DTW aligns two time series of arbitrary lengths by warping one time axis onto the other.
- The standard algorithm takes sequences S and Q as input and returns the DTW distance after filling the warping matrix.
- The sequences are represented as S = s_1, s_2, ..., s_n and Q = q_1, q_2, ..., q_m, where n and m are their lengths.
- Dynamic programming computes cumulative costs from subproblems using a recursion over neighboring warping-matrix cells.
- The algorithm first computes an n × m local-distance matrix, then fills the warping matrix and reports the minimum-cost path and distance.
- Valid paths must satisfy monotonicity, continuity, and boundary constraints, connecting the top-left and bottom-right matrix corners.
- Standard DTW may examine every warping-matrix cell, giving O(nm) space and time complexity.
4 Global Constraint (BandDTW)
BandDTW speeds up DTW by constraining the warping path to remain within a band around the warping matrix’s diagonal.
- BandDTW adds global constraints that limit how far the warping path may stray from the diagonal.
5 Divide and Conquer Technique (DC)
The Divide and Conquer (DC) technique reduces DTW’s space complexity by recursively splitting the alignment problem, but the described procedure can fail to recover the optimal warping path. Its behavior depends on how the middle point is selected, and the resulting paths can differ from standard DTW.
- DC retains O(mn) time complexity while reducing space complexity to O(m + n).It divides the alignment problem recursively and uses standard DTW for sufficiently small subproblems.
- DC selects a middle point in Q, combines forward and backward space-efficient alignment costs, and chooses the minimizing row as a split point.The split divides the warping matrix into two subproblems for recursive processing.
- For subproblems with sequences of length at most 2, DC calls standard DTW and concatenates the resulting alignments.
- Flooring the middle point causes infinite recursion because repeated splits produce the same subsequences.The paper contrasts this with rounding the middle point up, which still produces a path different from standard DTW in the example.
- Rounding the middle point up yields a warping path and DTW distance different from the standard DTW result in the example.The example’s shaded paths show that the DC and standard DTW paths are different.
6 Sparse Dynamic Programming Approach
SparseDTW reduces DTW space by quantizing similar values into bins, storing only relevant matrix entries, and opening additional cells when needed to preserve the optimal path. It computes warping costs and reconstructs the path through sparse dynamic programming, with worst-case O(nm) time and space reduced by a constant factor b.
- Sparse matrix construction: The algorithm initializes matrix cells from quantized values, then opens blocked cells when upper neighbors are unavailable, preserving connectivity without sacrificing optimality.Unblocking computes Euclidean distances for the relevant cells and changes them from blocked to unblocked.
- Quantization and bins: Overlapping bins are controlled by bin-width and resolution; these parameters affect space usage but do not affect alignment optimality.The example uses bin-width 0.5 and produces four bins.
- Sparse matrix construction: SparseDTW quantizes both time series and uses their similarity to build a sparse warping matrix instead of storing all n × m entries.The sparse matrix can require much less than n × m space when the sequences are similar.
- Cost computation: Warping costs are computed for each open cell from the minimum cost among its lower neighbors plus the cell’s local distance.Lower neighbors use linear indices c−1, c−n, and c−(n+1).
- Path reconstruction: The optimal path is recovered backward from the bottom-right matrix cell by repeatedly selecting the minimum-cost open lower neighbor until reaching SM(1).Considering only open cells may reduce the number of neighbors examined and potentially lower overall time.
- Complexity: SparseDTW reduces space complexity by a constant factor b, the number of bins, while retaining O(nm) worst-case time because every matrix cell may still be accessed.Standard DTW uses O(nm) space and time.
7 Experiments, Results and Analysis
Experiments compare SparseDTW with DTW, DC, and BandDTW on benchmark and synthetic datasets, evaluating space-time tradeoffs, correlation effects, scalability, and accuracy. SparseDTW uses fewer computed cells, exploits similarity, remains optimal, and handles datasets for which DTW exceeds memory limits.
- Experimental setup: Experiments compare SparseDTW with DTW, DC, and BandDTW using benchmark and synthetic datasets.Synthetic data controls correlation between sequences, while benchmark data comes from the UCR archive.
- Elapsed time: SparseDTW exploits inherent similarity in GunX and Trace, whereas DTW and BandDTW have similar time profiles and DC performs worst.DC’s poor performance is attributed to the large number of recursive calls used to generate and solve sub-problems.
- Computed cells: SparseDTW produces the lowest number of open or computed cells among the four evaluated algorithms.The computed-cell comparison measures time complexity and shows SparseDTW’s sparse computation pattern.
- Computed cells: SparseDTW outperforms DC, DTW, and BandDTW in computed cells even when the optimal paths are close to the diagonal.DC and DTW do not exploit data similarity, while BandDTW benefits from the near-diagonal paths but remains inferior to SparseDTW.
- Band width and length: Longer series increase computing time, and wider BandDTW bands require more cells to be opened.The series length enlarges the warping matrix, while band width directly affects CPU time.
- Large datasets: DTW is not applicable to datasets larger than 6K because storing its warping matrix exceeds available memory.The large-dataset comparison excludes BandDTW and DC because they do not guarantee optimality.
- Correlation: Extremely low-correlation sequences produce more open cells than extremely high-correlation sequences in SparseDTW.The experiment tests whether correlation affects elapsed time through the number of cells opened around the warping path.
- Accuracy: BandDTW errors range from 30% to 500%, while SparseDTW always returns the exact DTW distance.Different optimal paths may have different sizes; in the ERP example, both methods find paths with the same minimum distance.
8 Conclusions
The paper introduces SparseDTW, a sparse dynamic-programming algorithm that exploits correlation between time series to find optimal warping paths. Experiments on synthetic and real-life datasets demonstrate its reported efficiency and accuracy against DTW, BandDTW, and DC.
- Conclusion: SparseDTW is a sparse dynamic-programming technique for finding optimal warping paths between time series.The algorithm exploits correlation between the series while preserving optimality.
- Conclusion: SparseDTW always outperforms DTW, BandDTW, and DC in the reported experiments.The evaluation uses both synthetic and real-life datasets.