1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ DTW is harder to substitute this metric into. The assumption made in mine is representation in some vector space V with dim(V) > 1. It is a distinctly shape-based metric, making it slightly more difficult to combine with the edit-based flavor of DTW. Nevertheless, since DTW is ultimately a bizarre constrained optimization problem, I have hope for modifying it. $\endgroup$
    – Jason
    Nov 13, 2020 at 22:05
  • $\begingroup$ However, I still chose to go with DTW because I have concerns about the integrety of sliding window based time series distance measures such as MPdist, and as a shape based metric it only makes sense to compare it to other shape based metrics. Moreover, my preliminary brute force implementation did not show promising enough results to justify trying to modify a similarity join. $\endgroup$
    – Jason
    Nov 13, 2020 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.