Anomaly detection in long time series on high-performance cluster with GPUs

Currently, the discovery of anomalies in long time series occurs in a wide range of subject areas: digital industry, healthcare, climate modeling, financial analytics, etc. Discord formalizes the anomaly concept being defined as a time series subsequence that has a distance of at least r to its non-overlapping nearest neighbor, where r is a prespecified threshold. This article presents a new algorithm for discord discovery on a high-performance computing cluster, where each cluster node is equipped with a GPU. The algorithm employs the data parallelism concept: the time series is divided into disjoint fragments that are processed separetely by GPUs of the cluster nodes. Using a parallel algorithm previously developed by the authors, local candidates for discords are selected at each node. Further, through the data exchanges, a set of global candidates is formed at each node as a union of all local candidates. Then each node performs a global refinement, removing false-positive discords from the global candi date set. Global refinement is parallelized based on block multiplication of the candidate matrix and the subsequence matrix of the fragment. The resulting set of discords is formed as the intersection of the sets obtained by the nodes as a result of global refinement. Computational experiments with synthetic and real time series, carried out on the Lomonosov-2 and Lobachevsky supercomputers equipped with 48–64 GPUs, show the high scalability of the developed algorithm.