Parallelization of Dynamic Time Warping on a Heterogeneous Platform

Yao ZHENG  Limin XIAO  Wenqi TANG  Lihong SHANG  Guangchao YAO  Li RUAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A    No.11    pp.2258-2262
Publication Date: 2014/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.2258
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
dynamic time warping (DTW),  parallel algorithm,  graphics processing unit (GPU),  compute unified device architecture (CUDA),  

Full Text: PDF>>
Buy this Article

The dynamic time warping (DTW) algorithm is widely used to determine time series similarity search. As DTW has quadratic time complexity, the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms. In this paper, we present a parallel approach for DTW on a heterogeneous platform with a graphics processing unit (GPU). In order to exploit fine-grained data-level parallelism, we propose a specific parallel decomposition in DTW. Furthermore, we introduce an optimization technique called diamond tiling to improve the utilization of threads. Results show that our approach substantially reduces computational time.