Efficient Pattern-Based Time Series Classification on GPU

Kai-Wei Chang, Baplab Deka, W.-M. W. Hwu, and Dan Roth, in ICDM, 2012.

Download the full text

Abstract

Time series shapelet discovery algorithm finds subsequences from a set of time series for use as primitives for time series classification. This algorithm has drawn a lot of interest because of the interpretability of its results. However, computation requirements restrict the algorithm from dealing with large data sets and may limit its application in many domains. In this paper, we address this issue by redesigning the algorithm for implementation on highly parallel Graphics Process Units (GPUs). We investigate several concepts of GPU programming and propose a dynamic programming algorithm that is suitable for implementation on GPUs. Results show that the proposed GPU implementation significantly reduces the running time of the shapelet discovery algorithm. For example, on the largest sample dataset from the original authors, the running time is reduced from half a day to two minutes.

Bib Entry

@inproceedings{CDHR12,
  author = {Chang, Kai-Wei and Deka, Baplab and Hwu, W.-M. W. and Roth, Dan},
  title = {Efficient Pattern-Based Time Series Classification on GPU },
  booktitle = {ICDM},
  year = {2012}
}