Time-series anomaly detection using dynamic programming based longest common subsequence on sensor data

doi:10.1016/j.eswa.2022.118902

Time-series anomaly detection using dynamic programming based longest common subsequence on sensor data

2023-03-01

11

PRE

AI

T

Thi Phuong Quyen Nguyen *

DOI：10.1016/j.eswa.2022.118902

Original

Original request for help

Save

Abstract

En 中文

This study proposes a novel approach to time-series anomaly detection by solving the longest common subsequence (LCS) problem of two time-series data. The conventional LCS problem is used to measure the similarity of two input strings. However, it cannot be applied to real-time data collected from sensors in smart manufacturing, which are mostly real numbers instead of strings. Thus, two algorithms-an extension of fixed gap longest common subsequence (extent FGLCS) and the modified dynamic programming-based LCS (MDP-LCS) algorithm-are proposed to deal with real-time series data. Further, a gap search constraint is investigated to limit the search range in finding the LCS. This study also provides a threshold to define the matching of a pair that contains real numbers rather than a string in the conventional LCS or FGLCS problems. In addition, the proposed methods employ the gap search constraint and the threshold to reduce computational time. Furthermore, the proposed algorithms can be implemented on both univariate and multivariate time-series data. The LCS length, known as the similarity of the two time-series data, is used to detect the anomalies based on the user's expectation. The accuracy and computational time of the proposed algorithm show a significant positive result compared with the exact solution provided by the dynamic programming-based LCS algorithm. Moreover, this study also uses the proposed methods for anomaly detection in a case study of big multisensory data in smart manufacturing. The result shows that the MDP-LCS can detect approximately 98% of normal data and more than 85% of anomalies with a shorter computational time.

Keywords:

Anomaly detection

Dynamic programming

Fixed gap longest common subsequence

Longest common subsequence

Time-series

Time-series anomaly detection using dynamic programming based longest common subsequence on sensor data

Abstract

Journal

Organization