THAAD: Efficient matching queries under temporal abstraction for anomaly detection

Abstract In this paper, we present a novel algorithm and efficient data structure for anomaly detection based on temporal data. Time-series data are represented by a sequence of symbolic time intervals, describing increasing and decreasing trends, in a compact way using gradient temporal abstraction technique. Then we identify unusual subsequences in the resulting sequence using dynamic data structure based on the geometric observations supporting polylogarithmic update and query times. Moreover, we introduce a new parameter to control the pairwise difference between the corresponding symbols in addition to a distance metric between the subsequences. THAAD is evaluated on a large dataset of public DNS attacks and compared with a number of baseline algorithms. We find that THAAD outperforms other approaches, achieving up to 11% improvement in True Positive Rate (TPR) and False Negative Rate (FNR).