Monitoring Discord on Streaming Time-series

IPSJ

Bibliographic Information

Other Title
  • ストリーミング時系列データに対するディスコードモニタリング

Search this article

Description

近年，多くのアプリケーションは時系列データを生成しており，その時系列データを分析することに注目が集まっている．最も重要な時系列データの分析の1つに異常検知があり，ディスコードの発見は時系列データ中の異常なサブシーケンスの発見に対応する．ディスコードとは，時系列データの中のすべてのサブシーケンスの中で，最近傍のサブシーケンスとの距離が最大となるサブシーケンスである．時系列データは本質的に動的であるため，ストリーミング時系列データのディスコードをモニタリングすることは非常に重要である．本論文では，スライディングウィンドウ上でストリーミング時系列データのディスコードを効率的にモニタリングするSDM（Streaming Discord Monitoring）を提案する．また，SDMを近似アルゴリズムに拡張し，精度の保証をしたうえでより効率的にディスコードをモニタリングする．実データを用いた実験により，SDMおよびその近似アルゴリズムの有効性を確認する．

Many applications generate time-series, and time-series analysis has been receiving many attentions. One of the most important time-series analysis tools is anomaly detection, and discord discovery aims at finding an anomaly subsequence in a time-series. Given a time-series, the discord of the time-series is the subsequence with the largest distance to its nearest neighbor among all subsequences. Time-series is essentially dynamic, so monitoring the discord of a streaming time-series is an important problem. This paper addresses this problem and proposes SDM (Streaming Discord Monitoring), an algorithm that efficiently updates the discord of a streaming time-series over a sliding window. We show that SDM is approximation-friendly, i.e., the computational efficiency is accelerated by monitoring an approximate discord with theoretical bound. Our experiments on real datasets demonstrate the efficiency of SDM and its approximate version.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top