Discovery of Time Series Motifs on Intel Many-Core Systems

Abstract

A motif is a pair of subsequences of a longer time series, which are very similar to each other. Motif discovery is applied in a wide range of subject areas involving time series: medicine, biology, entertainment, weather prediction, and others. In this paper, we propose a novel parallel algorithm for motif discovery using Intel MIC (Many Integrated Core) accelerators in the case when time series fit in the main memory. We perform parallelization through thread-level parallelism and OpenMP technology. The algorithm employs a set of matrix data structures to store and index the subsequences of a time series and to provide an efficient vectorization of computations on the Intel MIC platform. The experimental evaluation shows the high scalability of the proposed algorithm.