A Parallel Discord Discovery Algorithm for a Graphics Processor.

The detection of anomalous subsequences in a time series is required today in a wide range of computationally intensive applications such as digital industry, the Internet of Things, personal medicine, etc. One of the most attractive approaches to solving this problem is the concept of discord—the subsequence of a time series with the greatest distance to its nearest neighbor—because it requires the analyst to set only one intuitive parameter (subsequence length). The previously proposed DRAG (discord range aware gathering) algorithm for finding discords is exact, but its parallel versions are absent for any hardware architecture. The paper proposes a new approach to parallelizing this algorithm for a graphics processing unit, which is called PD3 (parallel DRAG-based discord discovery). A data preprocessing phase was added to the PD3 to compute mean values and standard deviations of all subsequences of the time series. The results are used further at the candidate selection and refinement phases to calculate the distances between the subsequences of the time series. Each algorithm phase is parallelized separately on the basis of the data parallelism concept and using vector data structures. Experiments show that the PD3 is much ahead of competing parallel algorithms in terms of the average time taken to find one discord. [ABSTRACT FROM AUTHOR]