Parallel algorithm for time series motif discovery on graphic processor
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 9 (2020) no. 3, pp. 17-34
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
Keywords:
time series, motif discovery, parallel algorithm, NVIDIA GPU, OpenACC.
@article{VYURV_2020_9_3_a1,
author = {M. L. Zymbler and Ya. A. Kraeva},
title = {Parallel algorithm for time series motif discovery on graphic processor},
journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
pages = {17--34},
publisher = {mathdoc},
volume = {9},
number = {3},
year = {2020},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/VYURV_2020_9_3_a1/}
}
TY - JOUR AU - M. L. Zymbler AU - Ya. A. Kraeva TI - Parallel algorithm for time series motif discovery on graphic processor JO - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika PY - 2020 SP - 17 EP - 34 VL - 9 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/VYURV_2020_9_3_a1/ LA - ru ID - VYURV_2020_9_3_a1 ER -
%0 Journal Article %A M. L. Zymbler %A Ya. A. Kraeva %T Parallel algorithm for time series motif discovery on graphic processor %J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika %D 2020 %P 17-34 %V 9 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/VYURV_2020_9_3_a1/ %G ru %F VYURV_2020_9_3_a1
M. L. Zymbler; Ya. A. Kraeva. Parallel algorithm for time series motif discovery on graphic processor. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 9 (2020) no. 3, pp. 17-34. http://geodesic.mathdoc.fr/item/VYURV_2020_9_3_a1/