  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.
