A new discord definition and an efficient time series discord detection method using GPUs
Thuy Thi Thu Huynh, Anh Tuan Duong, Chau Thi Ngoc Vo · 2021
Discord is the most unusual subsequence in a time series. Most of the methods for discord detection in time series belong to the window-based category which uses a sliding window with a pre-specified length. Besides, a discord may appear twice or more times so that any instance of this discord does not qualify to be an abnormal. In addition, computational cost of window-based methods for discord detection is still high. In this paper, we propose a GPU-based parallel method, called KBF_GPU, for time series discord detection with a new definition of discord and no requirement for a pre-specified discord length. With the new discord definition, KBF_GPU can detect exactly the discord in case of there are more than one similar discords in time series. By using GPU programming techniques to parallelize Brute-Force algorithm with the new discord definition, our proposed KBF_GPU can run about 10,216 times faster than Brute-Force algorithm with the new discord definition on average over seven benchmark datasets.