Title: Efficient search for top-k discords in streaming time series

Authors: Bui Cong Giao; Duong Tuan Anh

Addresses: Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, 268 Ly Thuong Kiet, District 10, Ho Chi Minh City, Vietnam ' Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, 268 Ly Thuong Kiet, District 10, Ho Chi Minh City, Vietnam

Abstract: The problem of anomaly detection in streaming time series has received much attention recently. The problem addresses finding the most anomalous subsequence (discord) over a time-series stream, which might arrive at high speed. The fact that finding top-k discords is more useful than finding the most unusual subsequence since users might make a choice among the top-k discords instead of choosing only one. Hence, an efficient method of search for top-k discords in streaming time series is proposed in the paper. The method uses a lower bound threshold, a lower bounding technique on a common dimensionality reduction transform, and a state-of-the-art technique of the distance computation between two time-series subsequences to prune off unnecessary distance calculations. The three techniques are arranged in a cascading fashion to speed up the performance of the method. Furthermore, the proposed method can return a set of top-k discords on the fly. The experimental results show that the proposed method can acquire quality discords nearly identical to those obtained by HOT SAX, a well-known method of anomaly detection. Remarkably, our proposed method demonstrates a fast response in handling time-series streams at high speed.

Keywords: anomaly detection; discord; streaming time series.

DOI: 10.1504/IJBIDM.2020.107544

International Journal of Business Intelligence and Data Mining, 2020 Vol.16 No.4, pp.397 - 417

Received: 03 Jul 2017
Accepted: 30 Oct 2017
Published online: 01 Jun 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article