2021/02/09 by Matthieu Herrmann, Geoffrey I. Webb, Herrmann, Matthieu +1
Computer Science · #Time Series Analysis and Forecasting #Data Management and Algorithms #Advanced Text Analysis Techniques
paper · pdf · doi:10.48550/arxiv.2102.05221
Nearest neighbor search under elastic distances is a key tool for time series\nanalysis, supporting many applications. However, straightforward\nimplementations of distances require O(n2) space and time complexities,\npreventing these applications from scaling to long series. Much work has been\ndevoted to speeding up the NN search process, mostly with the development of\nlower bounds, allowing to avoid costly distance computations when a given\nthreshold is exceeded. This threshold, provided by the similarity search\nprocess, also allows to early abandon the computation of a distance itself.\nAnother approach, is to prune parts of the computation. All these techniques\nare othogonal to each other. In this work, we develop a new generic strategy,\n"EAPruned", that tightly integrates pruning with early abandoning. We apply it\nto six elastic distance measures: DTW, CDTW, WDTW, ERP, MSM and TWE, showing\nsubstantial speedup in NN search applications. Pruning alone also shows\nsubstantial speedup for some distances, benefiting applications beyond the\nscope of NN search (e.g. requiring all pairwise distances), and hence where\nearly abandoning is not applicable. We~release our implementation as part of a\nnew C++ library for time series classification, along with easy to use\nPython/Numpy bindings.\n