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

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.

Automated summary

This study proposes a novel approach for time-series anomaly detection using the longest common subsequence (LCS) problem. The proposed algorithms, extent FGLCS and MDP-LCS, are designed to handle real-time series data and achieve improved computational efficiency compared to existing methods.