Time Series Join on Most Correlated Subsequences Using MapReduce

In recent years, a large amount of time series have been generated in various industries, and time series contains important information. Time series refers to a series of ordered real numbers that were collected with equal time intervals. Time series join on subsequences means to find the most similar or most correlated subsequence pairs from two time series. Joining two time series on subsequences using Pearson correlation coefficient can provide more useful information than other similarity measures. However, finding the most correlated subsequences is a time consuming task. In order to decrease the runtime of finding the most correlated subsequence pairs, we propose an approach adopting MapReduce programming model in this paper. Our method includes four steps. First, computing the shift cross product matrix of two time series using a parallel FFT algorithm. Second, splitting the two time series into multiple subsequences. Third, partitioning the shift cross product matrix into blocks according to the time series splitting method. Finally, the join operations on subsequences are performed parallel. In experiment, we conducted extensive tests on real datasets to verify the effectiveness of our approach.