Sift - Dynamic Time Warping

Dynamic Time warping is a distance based algorithm that allows you to compare and measure similarity between two time based sequences, by minimizing the Euclidean distance between points. Essentially it aligns each point of one trace to a corresponding point on the other trace that require the least distance. All distances are added together to make the total cost function of the trace. The large the cost function, the less similar the two traces are. This can be useful when trying to identify a singular trace or to find outliers.

Mathematics of Dynamic Time Warping

Say you had a trace x of size N, and a trace y of size M, this is how you would calculate the cost matrix:

where d() is equal to the absolute distance.

To speed up the computational cost a Lower Bound Keogh algorithm was implemented.