This BSc thesis deals with speeding up distance calculations between time series. We deal with time series very often in computer science. They are one of the most common forms of data for machine learning. By recognizing trends within them, we can understand them better, split them into classes and prepare them for further research.
The contribution of this BSc thesis are new approaches for optimising dynamic time warping (DTW) algorithm by parallelizing its computation. Two approaches of optimisation are described. First approach is based on \textit{meet in the middle} principle, where we begin calculating from each end of time series and meet in the middle.
Second approach is based on changing the sequence of calculations in order to be able to compute each iteration of this dynamic programming problem in parallel.
First approach is easier to understand and implement and performs as expected even on shorter time series. Second approach is more complex to implement and because of technical limitations only gives optimal results on longer time series.
|
