Abstract: Elastic distances are key tools for time series analysis. Straightforward
implementations require O(n2)space and time complexities, preventing many
applications from scaling to long series. Much work hasbeen devoted in speeding
up these applications, mostly with the development of lower bounds, allowing to
avoid costly distance computations when a given threshold is exceeded. This
threshold also allows to early abandon the computation of the distance itself.
Another approach, developed for DTW, is to prune parts of the computation. All
these techniques are orthogonal to each other. In this work, we develop a new
generic strategy, "EAPruned", that tightly integrates pruning with early
abandoning. We apply it to DTW, CDTW, WDTW, ERP, MSM and TWE, showing
substantial speedup in NN1-like scenarios. Pruning also shows substantial
speedup for some distances, benefiting applications such as clustering where
all pairwise distances are required and hence early abandoning is not
applicable. We release our implementation as part of a new C++ library for time
series classification, along with easy to usePython/Numpy bindings.