Combining Dynamic Programming and GPU to accelerate k-Distance Discord Detection in Time Series Data
Nguyen Trong Nhan, Duong Tuan Anh, Jiří Dvorský · 2023
Detecting anomalous subsequences plays a vital role in time series analysis. Traditional approaches often rely on sliding windows to extract subsequences and identify anomalies. However, these methods encounter two difficulties: i) they are unable to address the "twin freak" problem and ii) they incur high computational costs when dealing with large time series datasets. We introduce a new method called DP_KBF_GPU to address the aforementioned challenge. Our method is designed for identifying K-Distance discords and effectively handle the "twin freak" problem commonly encountered. This method combines Dynamic Programming technique and Graphics Processing Units (GPUs) parallelization to enhance its performance. By employing Dynamic Programming with the Euclidean distance metric and leveraging the parallel processing capabilities of GPUs, our method achieves efficient computations. Experimental results on six benchmark time series datasets have demonstrated the high efficiency of our approach in timely detecting the most anomalous subsequences while maintaining high accuracy.