Alterable Similarity Join for Time Series I'm currently trying to implement the MPdist (matrix profile distance) algorithm for time-series data, but I've developed a new distance metric that I'd like to use in place of the Euclidean metric. I've implemented an algorithm that techincally works, however I used brute force to compute the distance between every subsequence of every time series that I'm using.
As such, it's horribly inefficient. I want to use a similiarity join algorithm to get complexity down. Still, they're really not my area of expertise and most algorithms I've seen are not very transparent and make critical use of Euclidean distance for calculating the 1NN similarity join.
Could someone point me to an article which is perhaps a little more transparent and is such that I could more easily replace the Euclidean metric with another? Or a github repo or something. I only need 1NN
Dynamic Time Warping might be what you're looking for: it measures similarity between two time series based on the optimal alignment between the two sequences. For example point $i$ in sequence 1 might be better aligned with point $i+3$ in sequence 2 based on the evolution of the sequences (as opposed to Euclidean distance which would always compare $i$ in seq. 1 with $i$ in seq. 2). The alignment method is inspired by the Levenshtein edit distance method, which can be implemented efficiently with dynamic programming.
There are many software implementations available.