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

Fingerprint

Chemical reactions
Time series
Dynamic programming

Keywords

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

ASJC Scopus subject areas

  • Engineering(all)

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

Efficient pattern-based time series classification on GPU. / Chang, Kai Wei; Deka, Biplab; Hwu, Wen-Mei W; Roth, Dan.

Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012. 2012. p. 131-140 6413748.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chang, KW, Deka, B, Hwu, W-MW & Roth, D 2012, Efficient pattern-based time series classification on GPU. in Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012., 6413748, pp. 131-140, 12th IEEE International Conference on Data Mining, ICDM 2012, Brussels, Belgium, 12/10/12. https://doi.org/10.1109/ICDM.2012.132
Chang KW, Deka B, Hwu W-MW, Roth D. Efficient pattern-based time series classification on GPU. In Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012. 2012. p. 131-140. 6413748 https://doi.org/10.1109/ICDM.2012.132
Chang, Kai Wei ; Deka, Biplab ; Hwu, Wen-Mei W ; Roth, Dan. / Efficient pattern-based time series classification on GPU. Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012. 2012. pp. 131-140
@inproceedings{8b093d25002d4057b54054faf3a4561d,
title = "Efficient pattern-based time series classification on GPU",
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.",
keywords = "Classification, GPU, Pattern-based classification, Time series",
author = "Chang, {Kai Wei} and Biplab Deka and Hwu, {Wen-Mei W} and Dan Roth",
year = "2012",
doi = "10.1109/ICDM.2012.132",
language = "English (US)",
isbn = "9780769549057",
pages = "131--140",
booktitle = "Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012",

}

TY - GEN

T1 - Efficient pattern-based time series classification on GPU

AU - Chang, Kai Wei

AU - Deka, Biplab

AU - Hwu, Wen-Mei W

AU - Roth, Dan

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Classification

KW - GPU

KW - Pattern-based classification

KW - Time series

UR - http://www.scopus.com/inward/record.url?scp=84874030981&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84874030981&partnerID=8YFLogxK

U2 - 10.1109/ICDM.2012.132

DO - 10.1109/ICDM.2012.132

M3 - Conference contribution

AN - SCOPUS:84874030981

SN - 9780769549057

SP - 131

EP - 140

BT - Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012

ER -