Developing a Pattern Discovery Method in Time Series Data and Its GPU Acceleration
The Dynamic Time Warping (DTW) algorithm is widely used in finding the global alignment of time series. Many time series data mining and analytical problems can be solved by the DTW algorithm. However, using the DTW algorithm to find similar subsequences is computationally expensive or unable to per...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Tsinghua University Press
2018-12-01
|
| Series: | Big Data Mining and Analytics |
| Subjects: | |
| Online Access: | https://www.sciopen.com/article/10.26599/BDMA.2018.9020021 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832572839584071680 |
|---|---|
| author | Huanzhou Zhu Zhuoer Gu Haiming Zhao Keyang Chen Chang-Tsun Li Ligang He |
| author_facet | Huanzhou Zhu Zhuoer Gu Haiming Zhao Keyang Chen Chang-Tsun Li Ligang He |
| author_sort | Huanzhou Zhu |
| collection | DOAJ |
| description | The Dynamic Time Warping (DTW) algorithm is widely used in finding the global alignment of time series. Many time series data mining and analytical problems can be solved by the DTW algorithm. However, using the DTW algorithm to find similar subsequences is computationally expensive or unable to perform accurate analysis. Hence, in the literature, the parallelisation technique is used to speed up the DTW algorithm. However, due to the nature of DTW algorithm, parallelizing this algorithm remains an open challenge. In this paper, we first propose a novel method that finds the similar local subsequence. Our algorithm first searches for the possible start positions of subsequence, and then finds the best-matching alignment from these positions. Moreover, we parallelize the proposed algorithm on GPUs using CUDA and further propose an optimization technique to improve the performance of our parallelization implementation on GPU. We conducted the extensive experiments to evaluate the proposed method. Experimental results demonstrate that the proposed algorithm is able to discover time series subsequences efficiently and that the proposed GPU-based parallelization technique can further speedup the processing. |
| format | Article |
| id | doaj-art-d005644bae204db0b1dd662186cad9e8 |
| institution | Kabale University |
| issn | 2096-0654 |
| language | English |
| publishDate | 2018-12-01 |
| publisher | Tsinghua University Press |
| record_format | Article |
| series | Big Data Mining and Analytics |
| spelling | doaj-art-d005644bae204db0b1dd662186cad9e82025-02-02T06:49:25ZengTsinghua University PressBig Data Mining and Analytics2096-06542018-12-011426628310.26599/BDMA.2018.9020021Developing a Pattern Discovery Method in Time Series Data and Its GPU AccelerationHuanzhou Zhu0Zhuoer Gu1Haiming Zhao2Keyang Chen3Chang-Tsun Li4Ligang He5<institution content-type="dept">Department of Computer Science</institution>, <institution>University of Warwick</institution>, <city>Coventry</city>, <country>UK</country>.<institution content-type="dept">Department of Computer Science</institution>, <institution>University of Warwick</institution>, <city>Coventry</city>, <country>UK</country>.<institution content-type="dept">Department of Computer Science</institution>, <institution>University of Warwick</institution>, <city>Coventry</city>, <country>UK</country>.<institution content-type="dept">School of Computer Science and Telecommunications Engineering</institution>, <institution>Jiangsu University</institution>, <city>Zhengjiang</city> <postal-code>212013</postal-code>, <country>China</country>.<institution content-type="dept">School of Computing and Mathematics</institution>, <institution>Charles Sturt University</institution>, <city>Wagga</city> <state>Wagga</state>, <country>Australia</country>.<institution content-type="dept">Department of Computer Science</institution>, <institution>University of Warwick</institution>, <city>Coventry</city>, <country>UK</country>.The Dynamic Time Warping (DTW) algorithm is widely used in finding the global alignment of time series. Many time series data mining and analytical problems can be solved by the DTW algorithm. However, using the DTW algorithm to find similar subsequences is computationally expensive or unable to perform accurate analysis. Hence, in the literature, the parallelisation technique is used to speed up the DTW algorithm. However, due to the nature of DTW algorithm, parallelizing this algorithm remains an open challenge. In this paper, we first propose a novel method that finds the similar local subsequence. Our algorithm first searches for the possible start positions of subsequence, and then finds the best-matching alignment from these positions. Moreover, we parallelize the proposed algorithm on GPUs using CUDA and further propose an optimization technique to improve the performance of our parallelization implementation on GPU. We conducted the extensive experiments to evaluate the proposed method. Experimental results demonstrate that the proposed algorithm is able to discover time series subsequences efficiently and that the proposed GPU-based parallelization technique can further speedup the processing.https://www.sciopen.com/article/10.26599/BDMA.2018.9020021dynamic time warpingtime series datadata miningpattern discoverygpgpuparallel processing |
| spellingShingle | Huanzhou Zhu Zhuoer Gu Haiming Zhao Keyang Chen Chang-Tsun Li Ligang He Developing a Pattern Discovery Method in Time Series Data and Its GPU Acceleration Big Data Mining and Analytics dynamic time warping time series data data mining pattern discovery gpgpu parallel processing |
| title | Developing a Pattern Discovery Method in Time Series Data and Its GPU Acceleration |
| title_full | Developing a Pattern Discovery Method in Time Series Data and Its GPU Acceleration |
| title_fullStr | Developing a Pattern Discovery Method in Time Series Data and Its GPU Acceleration |
| title_full_unstemmed | Developing a Pattern Discovery Method in Time Series Data and Its GPU Acceleration |
| title_short | Developing a Pattern Discovery Method in Time Series Data and Its GPU Acceleration |
| title_sort | developing a pattern discovery method in time series data and its gpu acceleration |
| topic | dynamic time warping time series data data mining pattern discovery gpgpu parallel processing |
| url | https://www.sciopen.com/article/10.26599/BDMA.2018.9020021 |
| work_keys_str_mv | AT huanzhouzhu developingapatterndiscoverymethodintimeseriesdataanditsgpuacceleration AT zhuoergu developingapatterndiscoverymethodintimeseriesdataanditsgpuacceleration AT haimingzhao developingapatterndiscoverymethodintimeseriesdataanditsgpuacceleration AT keyangchen developingapatterndiscoverymethodintimeseriesdataanditsgpuacceleration AT changtsunli developingapatterndiscoverymethodintimeseriesdataanditsgpuacceleration AT liganghe developingapatterndiscoverymethodintimeseriesdataanditsgpuacceleration |