Parallel algorithm for time series motif discovery on graphic processor

A time series motif is a pair of subsequences of the series that are most similar to each other. The problem of motif discovery occurs in a wide range of subject areas: medicine, biology, weather prediction, etc. The paper proposes a novel parallel algorithm for time series motif discovery on GPU for the case when the input data fit in the main memory. The proposed algorithm is based on the MK algorithm, which exploits the Euclidean distance and the triangle inequality to prune clearly unpromised pairs of subsequences without computation of the distance. MK decreases the running time up to several orders of magnitude in comparison to the most serial algorithms. However, the performance of MK decreases significantly when the time series length is greater then hundreds of thousands of elements. We designed matrix data structures that ensure the efficient parallel computations on GPU, and paralleled the calculations through the OpenACC programming technology. The results of experimental evaluation on synthetic and real-world datasets confirmed the high scalability of the developed algorithm.