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.

Original languageEnglish (US)
Title of host publicationProceedings - 12th IEEE International Conference on Data Mining, ICDM 2012
Pages131-140
Number of pages10
DOIs
StatePublished - 2012
Event12th IEEE International Conference on Data Mining, ICDM 2012 - Brussels, Belgium
Duration: Dec 10 2012Dec 13 2012

Other

Other12th IEEE International Conference on Data Mining, ICDM 2012
CountryBelgium
CityBrussels
Period12/10/1212/13/12

Keywords

  • Classification
  • GPU
  • Pattern-based classification
  • Time series

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Efficient pattern-based time series classification on GPU'. Together they form a unique fingerprint.

  • Cite this

    Chang, K. W., Deka, B., Hwu, W-M. W., & Roth, D. (2012). Efficient pattern-based time series classification on GPU. In Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012 (pp. 131-140). [6413748] https://doi.org/10.1109/ICDM.2012.132