ストリーミング時系列データに対するモチーフモニタリング

IPSJ

Bibliographic Information

Other Title
  • Motif Monitoring for Streaming Time-series

Search this article

Abstract

近年，多くのIoT機器はストリーミング時系列データを生成しており，それらを環境モニタリングやイベント検知に応用することが考えられる．これを実現する1つの技術として，時系列データの中に最も多く現れるサブシーケンスであるレンジモチーフの発見が注目を集めている．本論文では，カウントベースのスライディングウィンドウ上でストリーミング時系列データのレンジモチーフをモニタリングする問題に取り組む．ウィンドウがスライドした際，新たにサブシーケンスが生成され，最も古いサブシーケンスが削除される．生成および削除されるサブシーケンスとウィンドウ内のすべてのサブシーケンスを比較する単純な方法は，多くの類似度の計算を必要とするため効率的でない．そのため，効率的にモチーフを更新するアルゴリズムSRMMを提案する．SRMMの時間計算量は生成および削除されるサブシーケンスと類似するサブシーケンスの数にのみ依存し，効率的にレンジモチーフをモニタリングできる．4つの実データを用いた実験により，SRMMの有効性を確認した．

Recent IoT-based applications generate time-series in a streaming fashion, and they often require techniques that enable environmental monitoring and event detection from generated time-series. Discovering a range motif, which is a subsequence that repetitively appears the most in a time-series, is a promising approach for satisfying such a requirement. This paper tackles the problem of monitoring a range motif of a streaming time-series under a count-based sliding-window setting. Whenever a window slides, a new subsequence is generated and the oldest subsequence is removed. A straightforward solution for monitoring a range motif is to scan all subsequences in the window while computing their occurring counts measured by a similarity function. Because the main bottleneck is similarity computation, this solution is not efficient. We therefore propose an efficient algorithm, namely SRMM. SRMM is simple and its time complexity basically depends only on the occurring counts of the removed and generated subsequences. Our experiments using four real datasets demonstrate that SRMM scales well and shows better performance than a baseline.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top