DTW-Based Subsequence Similarity Search on AMD Heterogeneous Computing Platform

Subsequence similarity search is one of the most common subroutines in time series data mining algorithms. According to previous studies, Dynamic Time Warping (DTW) distance is the best distance measurement in many domains. However, the high computational complexity of DTW distance makes it a critical bottleneck in many subsequence similarity search applications. In some applications, the performance of software implementation still could not meet the high requirements of applications. Under the circumstance, some hardware implementations of DTW-based algorithms were proposed in the data mining community, using GPUs and FPGAs. In this paper, we propose a full system implementation for subsequence similarity search on AMD heterogeneous computing platform, including complete normalization pre-processing, two kinds of improved lower bound for pruning, and a novel segmented parallel DTW calculation process, which efficiently utilizes the capacity of CPU and GPU on the platform. Our work achieves one to two orders of magnitude speedup compared to software implementation and several times speedup to other GPU or FPGA implementations.