Monitoring Multiple Streams with Dynamic Time Warping using Graphic Processors
Department of Electrical Engineering, National Taiwan University
Parallel Data Mining Workshop (IPDM), 2011
@inproceedings{chang2011monitoring,
title={Monitoring Multiple Streams with Dynamic Time Warping using Graphic Processors},
author={Chang, J. and Yeh, M.Y.},
booktitle={Workshop Notes of the International Workshop on Parallel Data Mining},
pages={11},
year={2011}
}
In this paper, we present an approach for efficiently monitoring multiple data streams using graphic processor units (GPUs). Given reference patterns, similar subsequences in streams are matched under the dynamic time warping (DTW) distance and reported continuously. DTW distance is adopted since it offers scaling and shifting exibility in the time axis. However, it suffers from high computation complexity, not to mention online matching among multiple streams. To overcome these issues, we exploit the advantages of GPUs: high levels of parallelism at low cost. We first show how to speed up DTW in a parallel way by using GPUs in CUDA language. Then, according to the existing online subsequence method under DTW distance, we propose GSPRING, which conducts online matching in multiple streams with multiple patterns concurrently by utilizing the massive threads of GPUs. We demonstrate that with the experiments on the NVIDIA graphic cards, our proposed algorithm can achieve speedup of up-to-15-times compared to a CPU-based approach when nearly a thousand streams are monitored simultaneously.
December 28, 2011 by hgpu
