DEIM Forum 2019 D5-4

ストリーミング時系列データの効率的なディスコードモニタリングアルゴリズム
加藤 慎也†

天方 大地†

西尾 俊哉†

原隆浩†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5
E-mail: †{kato.shinya,amagata.daichi,nishio.syunya,hara}@ist.osaka-u.ac.jp
あらまし

近年，多くの IoT 機器はストリーミング時系列データを生成しており，それらを異常検知に応用することが考えられる．これを実現する一つの技術として，時系列データの中の各サブシーケンスに対して最近傍のサブシー
ケンスとの距離が最も大きいサブシーケンスであるディスコードの発見が注目を集めている．本稿では，カウントベー
スのスライディングウィンドウ上でストリーミング時系列データのディスコードをモニタリングする問題に取り組む．
ウィンドウがスライドした際，新たにサブシーケンスが生成され，最も古いサブシーケンスが削除される．これらのサブシーケンスにより，ウィンドウ内のサブシーケンスの最近傍のサブシーケンスが変化し，ディスコードが変化する可能性がある．しかし，ウィンドウがスライドするたびにウィンドウ内の全てのサブシーケンスに対して最近傍探索を実行する手法は，ディスコードの更新に多大な時間がかかる．そのため，効率的にディスコードを更新するアルゴリズム SDM を提案する．4 つの実データを用いた実験により，SDM の有効性を確認する．
キーワード ストリーミング時系列データ，ディスコードモニタリング

1 序論

近年，時系列データにおける外れ値の検出が注目を集めており，ディスコードの発見は外れ値を検出する最も重要な技術の一つである [5]．ある時系列データ t のディスコードとは，t を
長さ l のサブシーケンスに分割したとき，最近傍のサブシーケ
ンスとの距離が最大となるサブシーケンスである．例えば，図図 1: ディスコードの例

1 は心電図のストリーミング時系列データを表しており，赤いサブシーケンスがディスコードである．多くの IoT 機器はストリーミング時系列データを生成するため [9]，本稿では，ストsn および se により，ウィンドウ内のサブシーケンスの最近傍

リーミング時系列データのディスコードをモニタリングする問が変化し，ディスコードが変化する可能性がある．ディスコー

題に取り組む．

ドをモニタリングする単純な手法は，ウィンドウがスライドした際，ウィンドウ内の全てのサブシーケンスに対して最近傍探

アプリケーション例．心電図の時系列データをモニタリングする場合，このデータのディスコードをモニタリングすることで不整脈の検知を行うことができる．また，一般的に，ストリー

索を実行するものである．しかし，この手法はディスコードの更新に多大な時間がかかり，リアルタイム性を保証することが難しい．

ミング時系列データのディスコードをリアルタイムに検出することで，リアルタイムなデータクリーニングが可能であり，時提案アルゴリズムの概要．この問題を解決するため，カウン

系列データマイニングのタスクの精度を高めることができる．

トベースのスライディングウィンドウ上でディスコードを効率

上記のようなアプリケーションにおいて過去の全ての値を考慮する場合，過去に外れ値があったとき，その外れ値が常にディスコードとなり，新たな外れ値を検出できない可能性がある．そのため，カウントベースのスライディングウィンドウを的にモニタリングするアルゴリズム SDM (Streaming Discord

Monitoring) を提案する．SDM では，ウィンドウ内の各サブシーケンスに対して，最近傍および自身を最近傍とするサブシーケンスの情報を保持することで，ウィンドウのスライドにより最近傍が変化するサブシーケンスを効率的に発見する．

用いて最新の w 個の値のみを考慮し，それらのディスコード
をモニタリングする．ウィンドウがスライドした際，新たな値がウィンドウに挿入され，最も古い値がウィンドウから削除さ貢献．以下に本研究の貢献を示す．

•

カウントベースのスライディングウィンドウ上でストれる．つまり，新たな値を含むサブシーケンス sn が生成され，リーミング時系列データのディスコードをモニタリングする問

最も古い値を含むサブシーケンス se が削除される．このとき，題に取り組む．筆者らの知る限り，この問題はこれまでに取りと同様に，本研究においてもカウントベースのスライディング

組まれていない．

•

ウィンドウがスライドした際にディスコードを効率的に•ウィンドウを用いて，最新の w 個の値のみをモニタリングする．つまり，ウィンドウ内のストリーミング時系列データ t は更新するアルゴリズム SDM を提案する．

4 つの実データを用いた実験により，SDM の有効性を

t = (t[i], t[i + 1], ..., t[i + w − 1]) のように表され，t[i + w − 1]

確認する．

が最新の値である．また，l が与えられたとき，ウィンドウ内

本稿の構成．2 章で本稿の問題を定義し，3 章で関連研究につには w − l + 1 個のサブシーケンスが含まれる．ウィンドウがいて述べる．4 章で SDM について説明し，5 章で実データを用いた実験の結果を示す．最後に 6 章で本稿のまとめと今後の課題について述べる．

スライドしたとき，最新の l 個の値を含む新たなサブシーケン
スが生成される．同時に，最も古い値がウィンドウから削除されるため，最も古いサブシーケンスが削除される．本研究では，
このような環境において最近傍のサブシーケンスとの距離が最大となるサブシーケンスをモニタリングする. つまり，ウィン

2 予備知識2. 1 定ドウサイズ w のウィンドウに含まれる全てのサブシーケンスの義

集合を S ，サブシーケンス s の最近傍のサブシーケンスとの距

ス ト リ ー ミ ン グ 時 系 列 デ ー タ t は 実 数 値 の 系 列 で あ り，

t = (t[1], t[2], ...) と表現する．まず，t の中に現れる通常のパターンと異なるパターンを発見するため，t の一部を表すサ
ブシーケンスを定義する．

離を s.distN N としたとき，本研究の問題は以下のように定義される．
問題定義．t，l，および w が与えられたとき，式 (4) で表されるディスコード s∗ をモニタリングする．

定義 1（サブシーケンス）．t および長さ l が与えられたとき，s∗ = arg max s.distN N

p 番目のデータを始点とするサブシーケンス sp は式 (1) により

(4)

s∈S

定義される．

sp = (t[p], t[p + 1], . . . , t[p + l − 1])(1)

3 関連研究本章では，ディスコードの発見およびストリーミング時系列

ここで，sp の x 番目のデータの値を sp [x] と表現する．つまり，

sp = (sp [1], sp [2], · · · , sp [l]) である．次に，t の中で sp の最近
傍のサブシーケンスを計算するため，本研究では，時系列デー
タ間の距離を測る基本的な指標である z 正規化ユークリッド距

3. 1 ディスコードの発見
文献 [5] では，ディスコードを効率的に発見するアルゴリズム

HOT SAX を提案している．HOT SAX は，まず SAX によっ離を用いる．
定義 2（z 正規化ユークリッド距離）．長さ l の 2 つのサブシー
ケンス sp および sq が与えられたとき，これらの z 正規化ユー
クリッド距離 d(sp , sq ) は式 (2) により定義される．
v
u l (
)2
u∑ sp [i] − µ(sp )sq [i] − µ(sq )d(sp , sq ) = t−
σ(sp )σ(sq )
i=1

データのモニタリングに関する既存研究について紹介する．

てサブシーケンスを記号列に変換して管理する．そして，同じ記号列に変換されるサブシーケンス間の距離は小さくなる可能性が高いという性質を利用して，最近傍探索を高速化する．具
体的には，現時点でのディスコードの最近傍距離が D だとすると，あるサブシーケンスに対して最近傍探索を行うとき，そ(2)のサブシーケンスの最近傍距離が D 以下になった時点で，そのサブシーケンスはディスコードになり得ないため，以降の計

ここで，µ(s· ) および σ(s· ) はそれぞれ (s· [1], s· [2], ..., s· [l]) の算を打ち切ることができる．文献 [14] では，ディスク上の時系

平均および標準偏差である．

列データに対するディスコード発見アルゴリズムを提案していz 正規化ユークリッド距離の時間計算量は O(l) である．次に，る．文献 [14] の提案アルゴリズムは，ディスコードの候補を発

sp と sp+1 が互いに類似していることは自明であり，有用な結見するフェーズおよびディスコードの候補を絞り込むフェーズ

果を得るためには，このようなサブシーケンスを考慮すべきでからなる．ディスコードの候補を発見するフェーズでは，あるはない．そこで，互いに重なり合うサブシーケンスをトリビア

サブシーケンスと他のサブシーケンスとの距離が閾値 r 以下でルマッチと定義する [2], [11]．

ある場合，ディスコードにはなり得ないため候補から除外する．

定義 3（トリビアルマッチ）．sp が与えられたとき，sp とトリ
ビアルマッチであるサブシーケンスの集合 Sp は次の条件を満たす．

Sp = {sq |p − l + 1 <= p + l − 1}=q<

ディスコードの候補を絞り込むフェーズでは，候補間の距離を計算し，閾値 r 以下の場合，候補から除外する．一方，r 以上の場合，暫定のディスコードの最近傍距離を更新する．文献 [3]では，ディスコード発見を並列化することで高速化するアルゴ(3)

リズム PDD を提案している．PDD では，全てのサブシーケ

ここで，1 章で述べたアプリケーションを含む多くのアプリ

ンスを記号列に変換し，同じ記号列に変換されたサブシーケン

ケーションでは最新の値のみを考慮している [1], [7]．そのため，

スをグループ化する．グループ内のサブシーケンスの数が少な

ストリーミング時系列データに関する既存の研究 [4], [6], [10]い順に計算ノードに割り当てる．各計算ノードでは，グループ

内のサブシーケンスに関して最近傍探索を行い，最も最近傍距𝑠3

離が大きいサブシーケンスを求める．グループ内の計算をすべ𝑠1て終えると，他の計算ノードと通信を行い，暫定のディスコー
ドの最近傍距離を更新する．グループ内のサブシーケンスの数

𝑠2

𝑠4

𝑠7
𝑠6

が少ない順に計算していくため，早い段階で暫定のディスコー
ドの最近傍距離が大きくなり，暫定のディスコードの最近傍距
𝑠5離による枝刈りを効率的に行うことができる．しかし，これらの研究は，静的な時系列データを対象としている．

𝑠3

文献 [13] では，データの追加に対応したディスコードをモニ𝑠2
𝑠1

タリングするアルゴリズムを提案している．文献 [13] の提案ア𝑠4𝑠7

されるサブシーケンスに対して R 木を用いた最近傍探索を行

𝑠6

𝑠9う．そして，新たに生成されるサブシーケンスの最近傍距離が更新する．文献 [15] では，Matrix Profile と呼ばれるインデッ

2, 1.01, 1.01, 1.11, 1.76, 3.34, 3.18, 5.25, 3.5

識別子

NNタプル

1
2
3
4
5
6
7
8
9

2, 1.01, 1.01, 1.11, 1.79, 0.94, 3.19, 2.89, 2.25, 0.9(a) s9 生成前

3. 2. 1 ディスコードのモニタリング

ディスコードの最近傍距離よりも大きい場合はディスコードを

NNタプル

1
2
3
4
5
6
7
8

𝑠8

3. 2 ストリーミング時系列データのモニタリング

ルゴリズムでは，サブシーケンスを R 木で管理し，新たに生成

識別子

𝑠5

𝑠8

クスを用いてデータの追加に対応したディスコードをモニタリ(b) s9 生成後ングするアルゴリズムを提案している．このインデックスは，

図 2: サブシーケンス生成時の例

全てのサブシーケンスに対して最近傍のサブシーケンスとの距離を保持する．新たなサブシーケンスが生成されると，そのサブシーケンスに対して最近傍探索を行い，Matrix Profile を更新する．そして，Matrix Profile が最大となるサブシーケンスがディスコードとなる．これらの研究はデータの削除には対応していない．

3. 2. 2 スライディングウィンドウ上でのストリーミング時
系列データのモニタリング
文献 [10] では，カウントベースのスライディングウィンドウ
上でペアモチーフをモニタリングする問題に取り組んでいる．
ペアモチーフとは，時系列データの中で最も類似するサブシー
ケンスのペアである．文献 [10] の提案アルゴリズムでは，ペア
モチーフを高速に更新するため，各サブシーケンスは近傍のササブシーケンス se が削除される．sn が生成されるとき，ウィンドウ内の各サブシーケンスの最近傍のサブシーケンスが変化
し，ディスコードが変化する場合がある．また，se が削除されるときも同様にディスコードが変化する場合がある．さらに，

se がディスコードの場合，つまり，ディスコードが削除される
とき，ウィンドウ内の全てのサブシーケンスに対して，それらの最近傍のサブシーケンスを計算する必要がある．

4.1 節において sn が生成される際の処理を説明し，4.2 節において se が削除される際の処理を説明する．4.3 節においてSDM の全体的なアルゴリズムを紹介し，SDM の計算量について述べる．最後に，4.4 節において，SDM の最悪更新時間を小さくするアルゴリズム I-SDM について説明する．

ブシーケンスのリストおよび逆最近傍のサブシーケンスのリス
トを保持する．また，文献 [6] では，ペアモチーフをモニタリン

4. 1 sn の生成グするためにデータ構造を最適化したアルゴリズムを提案して新たなサブシーケンス sn が生成されたとき，ウィンドウ内

おり，文献 [10] のアルゴリズムより優れた性能を示している．

の各サブシーケンスの最近傍のサブシーケンスが変化するか

文献 [4] では，カウントベースのスライディングウィンドウ上

どうかを効率的に把握するため，SDM では，ウィンドウ内のでレンジモチーフをモニタリングする問題に取り組んでいる．

各サブシーケンスに対して最近傍の情報である NN (Nearest

レンジモチーフとは，時系列データの中で最も多く現れるサブ

Neighbor) タプルを管理する．

シーケンスである．文献 [4] の提案アルゴリズムでは，ウィンドウ内のサブシーケンスを Piecewize Aggregate Approximation
で圧縮後，kd 木で管理している．kd 木を用いた範囲検索によりレンジモチーフが更新されるかどうかを高速に把握できる．

定義 4（NN タプル）．sp の NN タプル sp .⟨id, dist⟩N N は，

sp の最近傍のサブシーケンスの識別子（id）と最近傍のサブシーケンスとの距離（dist）で構成される．
つ ま り，sn が 生 成 さ れ た と き ，sp ∈ S\{sn } に 対 し て ，

4 SDM: Streaming Discord Monitoring

dist(sn , sp ) < sp .distN N ならば，sp の最近傍は sn に変化
し，sp .⟨n, dist(sn , sp )⟩N N となる．

ウィンドウがスライドした際，新たな値がウィンドウに挿入され，最も古い値がウィンドウから削除される．つまり，新たな値を含むサブシーケンス sn が生成され，最も古い値を含む

例 1．図 2 に，サブシーケンスの生成による，各サブシーケン
スの NN タプルの変化の例を示す．図 2 では，長さ 2 のサブ
シーケンスを 2 次元上の点として表現している．また，あるサ識別子

NNolder
タプル

NNyounger NNタプル
タプル

1
2
3
4

識別子

2, 1.02, 1.01

1, 1.01, 1.14, 1.66, 2.91, 1.01, 1.11, 1.76, 3.06, 3.31, 1.76, 3.32
3
4

7, 5.34, 3.1

68, 5.28, 5.25, 3.5789

5
6

4, 3.17
85, 3.5(a) s9 生成前

NNolder
タプル

NNyounger NNタプル
タプル

ンスの NN タプル，NNolder タプル，および NNyounger タプ

2, 1.02, 1.0ルの変化の例を示す．時刻 t において，s7 がディスコードで

1, 1.01, 1.14, 1.66, 2.91, 1.01, 1.1

あり，上で述べたように，NNyounger タプルと NN タプルが1, 1.76, 3.09, 0.91, 1.79, 0.94, 3.19, 3.24, 3.19, 2.89, 2.89, 2.2を更新する．同様に，s6 ，s7 ，および s8 の NNyounger タプルを

5, 0.9

タプルを更新する．

5

9, 2.25, 0.9(b) s9 生成後

図 3: NNolder タプルおよび NNyounger タプルの使用例

等しい場合，NNolder タプルは保持しない．時刻 t + 1 に新たに s9 が生成され，s9 に対して最近傍探索を行う．このとき，dist(s9 , s5 ) < s5 .distN Nyounger であるため，NNyounger タプル
更新する．さらに，distN N > distN Nyounger である場合，NN

4. 2 se の 削 除
サブシーケンス se が削除されたとき，se を最近傍としていた
サブシーケンスの最近傍が変化する．そこで，ウィンドウ内のブシーケンス si から sj への矢印は sj が si の最近傍であるこ

各サブシーケンスに対して，自身を最近傍とするサブシーケンとを表しており，例えば，s6 の最近傍は s4 である．時刻 t にスの識別子のリスト RL (Reverse Nearest Neighbor List) をおいて，s7 がディスコードである．時刻 t + 1 に新たに s9 が生保持すると，se が削除される際に，ウィンドウ内のサブシーケ

成され，s5 ，s7 ，および s8 の NN タプルが変化する．これにンスの最近傍が変化するかどうかを効率的に把握できる．つまより，s6 .distN N が最も大きい値となるため，ディスコードはり，あるサブシーケンス sp の RL RLp は以下の条件を満たす．

s6 に変化する．
sn が生成されるとき，sn とウィンドウ内の全サブシーケン
スとの距離計算を行うことで，sn の最近傍を計算する．そのため，ウィンドウ内のサブシーケンスは，自身より前に生成されたサブシーケンスに対する最近傍，および自身より後に生成されたサブシーケンスに対する最近傍を別々に保持したとすると，自身より後に生成されたサブシーケンスに対する最近傍を常に正確に保持することができる．そこで，各サブシーケンスに対して，自身より前に生成されたサブシーケンスに対する最近傍（NNolder タプル），および自身より後に生成されたサブシーケ
ンスに対する最近傍（NNyounger タプル）を管理する．
定義

5（NNolder タ プ ル ） ．sp の NNolder タ プ ル

sp .⟨id, dist⟩N Nolder は，sp より前に生成されたサブシーケンスに対する sp の最近傍のサブシーケンスの識別子（id）と最近傍のサブシーケンスとの距離（dist）で構成される．

RLp = {q|sq .idN N = p}

(5)

se が削除されるとき，se より前に生成されたサブシーケンスはすでに削除されているため，RL は自身より後に生成されたサブシーケンスの識別子のみを管理すればよい．また，se が削除される際に，RLe に含まれるサブシーケンスの最近傍が変化するが，sp .distN Nyounger がディスコードの最近傍距離より小さい場合，sp の最近傍の計算をすることなく sp がディスコー
ドにならないことがわかる．
例 3．図 4 に，サブシーケンスの削除による，各サブシーケ
ンスの NN タプル，NNolder タプル，NNyounger タプル，および RL の変化の例を示す．時刻 t において，s6 がディスコー
ドである．時刻 t + 1 において，s1 が削除されるとき，RL1に 2，3，および 4 が格納されているため，s2 ，s3 ，および s4の NNolder タプルおよび NN タプルが変化する．このとき，s∗ .distN N > s2 .distN Nyounger であるため，s2 に対して最近傍定 義 6（NNyounger タ プ ル ） ．sp の NNyounger タ プ ル

探索を行わずに，s2 がディスコードにならないことがわかる．

sp .⟨id, dist⟩N Nyounger は，sp より後に生成されたサブシーケ

同様に，s3 および s4 もディスコードにならないことがわかる．

ンスに対する sp の最近傍のサブシーケンスの識別子（id）と最近傍のサブシーケンスとの距離（dist）で構成される．
定義 4，5，および 6 より以下の補題が成り立つ．

4. 3 アルゴリズム
本節では SDM の詳細を紹介する．ウィンドウがスライドした際，まず，削除されるサブシーケンス se に対する処理を行

補題 1．sp .distN Nolder < sp .distN Nyounger ⇔ sp .⟨·, ·⟩N N =い，その後，新たに生成されるサブシーケンス sn に対する処sp .⟨·, ·⟩N Nolder

理を行う．

補題 2．sp .distN Nolder > sp .distN Nyounger ⇔ sp .⟨·, ·⟩N N =se に対する処理．アルゴリズム 1 は，SDM の se に対する処sp .⟨·, ·⟩N Nyounger

理を行うアルゴリズムを示している．se が与えられたとき，こ こ で ，あ る サ ブ シ ー ケ ン ス sp に 対 し て ，sp .⟨·, ·⟩N N =ウィンドウ内のサブシーケンスの集合 S から se を削除する

sp .⟨·, ·⟩N Nyounger が成り立つ場合，sp .idN Nyounger より前に生成されたサブシーケンスが sp の最近傍となることはないた（1 行）．se がディスコード s∗ である場合，Discord-Update を実行し，s∗ を取得する（2–3 行）．Discord-Update の詳細はめ，sp .⟨·, ·⟩N Nolder を保持する必要はない．

後述する．次に，RLe に対する処理を行う（4–9 行）．se の例 2．図 3 に，サブシーケンスの生成による，各サブシーケ

NN タプル sp .⟨·, ·⟩N N が変化するため，初期化を行う．次に，削除により，sp の NNolder タプル sp .⟨·, ·⟩N Nolder および sp の

識別子

𝑠2

𝑠3

2
3
4

𝑠4

𝑠6

𝑠9

NNyounger NNタプル

タプル

タプル

1

𝑠1
𝑠7

NNolder2, 1.02, 1.01, 1.01, 1.14, 1.66, 2.91, 1.01, 1.11, 1.76, 3.09, 0.91, 1.79, 0.99, 3.24, 3.19, 2.89, 2.89, 2.2

5
6
7
8
9

𝑠5

𝑠8

4, 3.19, 2.25, 0.9RL

Algorithm 2: SDM (insertion case)2, 3, 4

Input: sn : the new subsequence
Output: s∗ : the discord

61

S ← S ∪ {sn }2sn .⟨·, ·⟩N N ← ∅, sn .⟨·, ·⟩N Nolder ← ∅,9sn .⟨·, ·⟩N Nyounger ← ∅3

NNSearch(sn )4if sn .distN N > s∗ .distN N then55, 0.9s∗ ← sn(a) s1 削除前
識別子

𝑠2

𝑠3

タプル

𝑠6

6
7
8
9

𝑠5
𝑠8

4, 3.1

Input: sp : a subsequence
16, 3.09, 0.99, 0.99, 3.24, 3.19, 2.89, 2.89, 2.29, 2.25, 0.9Algorithm 3: NNSearch(sp )RL4, 1.66, 2.95𝑠4𝑠9NNyounger NNタプル

タプル

2
3
4

𝑠1
𝑠7

NNolderfor ∀sq ∈ S such that p > q do

62d ← dist(sp , sq )93

if sp .distN Nolder > d then4

sp .⟨·, ·⟩N Nolder ← ⟨q, d⟩5

if sq .distN Nyounger > d then5, 0.96sq .⟨·, ·⟩N Nyounger ← ⟨p, d⟩7

if sq .distN N > sq .distN Nyounger then8

if sq .⟨·, ·⟩N N = sq .⟨·, ·⟩N Nolder then(b) s1 削除後

9

RLsq .idN N ← RLsq .idN N \{q}図 4: サブシーケンス削除時の例

10sq .⟨·, ·⟩N N ← sq .⟨·, ·⟩N Nyounger

11

if sq = s∗ thens∗ ← Discord-Update

12

Algorithm 1: SDM (expiration case)
Input: se : the expired subsequence
1
2
3

13

S ← S\{se }14

sp .⟨·, ·⟩N N ← sp .⟨·, ·⟩N Nolder

if se = s∗ then15

RLsp .idN N ← RLsp .idN N ∪ {p}s∗ ← Discord-Update

16
17

for ∀p ∈ RLe do

4

if sp .distN Nolder < sp .distN Nyounger thenOutput: s∗ : the discord5

sp .⟨·, ·⟩N Nolder ← ∅, sp .⟨·, ·⟩N N ← ∅6

if s∗ .distN N < sp .distN Nyounger thenelse
sp .⟨·, ·⟩N N ← sp .⟨·, ·⟩N Nyounger

7

NNSearch(sp )最近傍探索．アルゴリズム 3 は，最近傍探索を行うアルゴリズ

8

if s∗ .distN N < sp .distN N then

ムを示している．sp と p > q を満たす sq との距離 d を計算し，

9s∗ ← spsp .⟨·, ·⟩N Nolder を更新する（2–4 行）．sq .distN Nyounger より dが小さい場合，sq .⟨·, ·⟩N Nyounger を更新する（5–6 行）．さらに，

sq .distN N より sq .distN Nyounger が大きい場合，sq .⟨·, ·⟩N N を
sp .distN Nyounger が s∗ .distN N より小さい場合，sp はディス

更新し，sq .⟨·, ·⟩N N = sq .⟨·, ·⟩N Nolder 場合，つまり RLsq .idN N

コードになり得ないため，処理を終了する．sp .distN Nyounger がに q 含まれている場合，RLsq .idN N から q を削除する（7–s .distN N より大きい場合，sp はディスコードになり得るため，

10 行）．また，sq が s∗ である場合，ディスコードが変化

sp に対して最近傍探索 NNSearch(sp ) を実行する．NNSearch

する可能性があるため，Discord-Update を実行する（11–12∗∗の詳細は後述する．sp の最近傍距離が s .distN N より大きい行 ）．sp .distN Nolder が sp .distN Nyounger よ り 小 さ い 場 合 ，

sp .⟨·, ·⟩N Nolder を sp .⟨·, ·⟩N N に代入し，RLsp .idN N に p を追∗場合，sp を s とする．

sn に対する処理．アルゴリズム 2 は，SDM の sn に対する処理を行うアルゴリズムを示している．sn が与えられたとき，ウィンドウ内のサブシーケンスの集合 S に sn を追加し，加する（13–15 行）．sp .distN Nolder が sp .distN Nyounger より大きい場合，sp .⟨·, ·⟩N Nyounger を sp .⟨·, ·⟩N N に代入する（16–17 行）．

sn .⟨·, ·⟩N N ,sn .⟨·, ·⟩N Nolder ,sn .⟨·, ·⟩N Nyounger を初期化する（1–ディスコードの更新．アルゴリズム 4 は，ディスコードの更新を

2 行）．次に，sn に対して NNSearch(sn ) を実行する（3 行）．

行うアルゴリズムを示している．まず，暫定のディスコードの

sn distN N が s .distN N より大きい場合は，sn を s とする

NN タプル s∗temp .⟨·, ·⟩N N を初期化する（1 行）．ウィンドウ内の（4–5 行）．

サブシーケンスをスキャンし，sp .⟨·, ·⟩N N = ∅ であるサブシー∗∗

ケンスを distN Nyounger を降順に格納するヒープ H に追加する

表 1: パラメータ設定

Algorithm 4: Discord-Update
Output: s∗temp : a temporal discord

パラメータ

値

1

s∗temp .⟨·, ·⟩N N ← ⟨−1, 0⟩

ディスコード長，l50, 100, 150, 200

2for ∀sp ∈ S do

ウィンドウサイズ，w [×103 ]5, 10, 15, 20

3

if sp .⟨·, ·⟩N N = ∅ then4

Up-Max-Heap(H, sp )

5
6

9
10
11
12

SDM において，NN タプルを保持しないサブシーケンスの

if s∗temp .distN N < sp .distN N thens∗temp ← sp

7

8

4. 4 I-SDM

else

数が多い場合，Discord-Update 実行時の最近傍探索の実行回数が多くなることで，ディスコードの最悪更新時間が大きくなる

while H =| ∅ do可能性がある．そこで，本節では，SDM におけるディスコード

sp ← Down-Max-Heap(H)の最悪更新時間を小さくするアルゴリズム I-SDM を提案する．

if s∗temp .distN N > sp .distN Nyounger thenI-SDM では，サブシーケンスの削除により最近傍が変化し，

break

NN タプルが空となった場合，そのサブシーケンスをリストに

else

13

NNSearch(sp )追加する．そして，サブシーケンス削除時に一度も最近傍探索14

if s∗temp .distN N < sp .distN N thenが実行されない場合，そのリストから一つサブシーケンスを取1516s∗temp ← sp

り出し，そのサブシーケンスに対して最近傍探索を実行する．
このようにして，Discord-Update 実行時の最近傍探索の実行回

return s∗temp

数を削減できる．

（3–4 行）．sp .⟨·, ·⟩N N = ∅ であるサブシーケンス sp の最近傍距
離が s∗temp .distN N よりも大きい場合，sp を s∗temp とする（5–7行）．次に，ヒープ H に関する処理を行う（8–15 行）．H の先頭から 1 つサブシーケンス sp を取り出し，sp .distN Nyounger がs∗temp .distN N より小さい場合，sp および H 内のサブシーケン
スはディスコードにならないため，処理を終了する（9–11 行）．

sp .distN Nyounger が s∗temp .distN N より大きい場合，sp はディスコードになる可能性があるため，NNSearch(sp ) を実行する（13 行）．sp .distN N が s∗temp .distN N より大きい場合，sp を5 性能評価本章では，SDM および I-SDM の性能評価のために行った実験の結果を紹介する．SDM および I-SDM の性能を評価するため，以下のアルゴリズムとの比較を行った．

N-SDM．N-SDM では，ウィンド内の各サブシーケンスは NN
タプルおよび RL を保持する．サブシーケンス生成時は SDMと同様の処理を実行し，サブシーケンス削除時は RL によって最近傍が変化するサブシーケンスを特定し，そのサブシーケンs∗temp とする（14–15 行）．最後に，s∗temp を返却する（16 行）．

スに対して最近傍探索を実行する．また，ディスコードが変化

時間計算量．サブシーケンス間の距離計算には O(l) 時間かか

タプルをスキャンし，最近傍距離が最大となるサブシーケンス

り，ウィンドウ内には w − l + 1 個のサブシーケンスがある．

をディスコードとする．

する可能性がある場合，ウィンドウ内のサブシーケンスの NN

そのため，NNSearch には O(wl) 時間かかる．Discord-Updateにおける H の構築では，最大 w − l + 1 回ヒープへの挿入が

5. 1 実 験 環 境

行われるため O(w log w) 時間かかる．また，H 構築後の処理

本実験は，Windows 10 Pro for Workstations，3.00GHz In-

では，最大 w − l + 1 回 NNSearch が実行されるため，O(w l)tel Xeon Gold，および 512GB RAM を搭載した計算機で行22

時間かかる．そのため，Discord-Update には O(w l) 時間かかる．アルゴリズム 1 において，Discord-Update が実行される
とき，O(w2 l) 時間かかり，また，|RLe | 回 NNSearch 実行される．|RLe | は最大 w − l であるため，アルゴリズム 1 の時間計
算量は O(w2 l) となる．アルゴリズム 2 は，NNSearch が一度実行されるため，時間計算量は O(wl) となる．以上より，SDMの時間計算量は O(w2 l) となる．
空間計算量．ウィンドウ内の各サブシーケンスは，NN タプル，

NNolder タプル，NNyounger タプル，および RL を保持する．各
サブシーケンスの保持する NN タプル，NNolder タプル，および NNyounger タプルの空間計算量は O(w) であり，各サブシー
ケンスの RL の要素数の合計は高々w − l 個であるため，SDMの空間計算量は O(w) となる．

い，全てのアルゴリズムを C++で実装した．
データセット．以下の 4 つの実データを用いた．

•

Google-CPU [12]: Google のデータセンタの CPU 使用

率の時系列データ（長さ 133,902）•

Google-Memory [12]: Google のデータセンタのメモリ

使用率の時系列データ（長さ 133,269）•

GreenHouseGas [8]: カリフォルニア州の温室効果ガスの排出量の時系列データ（長さ 100,062）•

ECG 1 : 心電図の時系列データ（長さ 100,000）

パラメータ．本実験で用いたパラメータを表 1 に示す．太字で表されている値はデフォルトの値である．また，あるパラメー

1：http://timeseriesclassification.com/index.php

50

SDM

100

150

N-SDM

I-SDM

200

SDM

更新時間 [msec]

160
140
120
100
80
60
40
20
0
50

100

150

N-SDM

I-SDM

160
140
120
100
80
60
40
20
0

200

50

100

150

ディスコード長(a) Google-CPU(b) Google-Memory(c) GreenHouseGas

最悪更新時間 [msec]

SDM

2500
2000
1500

1000
500
0
50

100

150

I-SDM

2500
2000
1500

1000
500
0

200

50

ディスコード長(e) Google-CPU

N-SDM

3000

SDM

100

150

200

N-SDM

50

I-SDM

2500
2000
1500

1000
500
0
100

150

ディスコード長

ディスコード長(f) Google-Memory(g) GreenHouseGas

100

150

200

(d) ECG

3000

50

I-SDM

ディスコード長SDM

最悪更新時間 [msec]

I-SDM

最悪更新時間 [msec]

N-SDM

N-SDM

160
140
120
100
80
60
40
20
0

200

ディスコード長

3000

SDM

平均更新時間 [msec]

I-SDM

ディスコード長SDM

最悪更新時間 [msec]

N-SDM

平均更新時間 [msec]

平均更新時間 [msec]

SDM
160
140
120
100
80
60
40
20
0

200

N-SDM

I-SDM

3000
2500
2000
1500

1000
500
0
50

100

150

200

ディスコード長(h) ECG

図 5: l の影響（(a)–(d)：平均更新時間，(e)–(h：最悪更新時間）

タの影響を調べるとき，他のパラメータは固定する．
評価指標．1 スライド当たりの平均更新時間，および最悪更新
時間を評価する．

GreenHouseGas において，SDM の最悪更新時間が大きいのは
上記の理由によるものである．I-SDM では，ディスコードが変化する際の最近傍探索の実行回数が SDM より小さくなっており，いずれのデータセットにおいても，他のアルゴリズムより

5. 2 評 価 結 果
l の影響．図 5 に l を変化させたときの結果を示す．全てのアルゴリズムにおける平均更新時間は，l の増加に伴い，線形に増加する．これは，l の増加に伴い，サブシーケンス間の距離の計算時間が大きくなり，最近傍探索にかかる時間が増加するからである．また，平均更新時間は常に N-SDM が最大であり，次に I-SDM が大きく，SDM が最小となっている．これは，サブシーケンス削除時，N-SDM では RL に含まれる全てのサ
ブシーケンスに対して最近傍探索を実行するが，SDM および

I-SDM ではディスコードになり得るサブシーケンスに対してのみ最近傍探索を実行するからである．また，サブシーケンス
削除時，SDM では一度も最近傍探索が実行されない場合があるが，I-SDM ではそのような場合，NN タプルを保持しないサ
ブシーケンスに対して最近傍探索を実行するため，I-SDM の
平均更新時間は SDM より大きくなる．
最悪更新時間は，l の増加に伴って増加する傾向がある．これは，l の増加に伴い，サブシーケンス間の距離の計算時間が大きくなるからである．一方で，最悪更新時間が l の増加に伴って減少する場合もあるが，これは，l によって RL のサイズが偏ったり，ディスコードが変化する場合に必要な最近傍探索の回数が変化するからである．N-SDM では，削除されるサ
ブシーケンスの RL が大きいとき，最近傍探索の実行回数が増

最悪更新時間が小さくなっている．

w の影響．図 6 に w を変化させたときの結果を示す．全てのアルゴリズムにおける平均更新時間は，w の増加に伴い，線形に増加する．これは，w の増加に伴い，ウィンドウ内のサブシー
ケンスの数が増加し，最近傍探索にかかる時間が増加するからである．また，l を変化させたときと同様の理由で，平均更新時
間は常に N-SDM が最大であり，次に I-SDM が大きく，SDMが最小となっている．
最悪更新時間は，w の増加に伴って増加する傾向がある．これは，w の増加に伴い，ウィンドウ内のサブシーケンスの数が増加し，最近傍探索にかかる時間が増加するからである．また，l を変化させたときと同様の理由で，w の増加に伴って最悪更新時間が減少する場合もある．I-SDM では，ディスコード
が変化する際の最近傍探索の実行回数が SDM より小さくなっており，いずれのデータセットにおいても，他のアルゴリズム
より最悪更新時間が小さくなっている．Google-CPU および

Google-Memory において，最悪更新時間は N-SDM が最大であり，次に SDM が大きくなっている．これは，ディスコードが変化する際の最近傍探索の影響よりも，サブシーケンス削除時の最近傍探索の影響が大きいからである．一方，GreenHouseGas
および ECG においては，N-SDM と SDM の最悪更新時間が逆転している場合がある．これは，w によってサブシーケンス

加し，最悪更新時間が悪くなる．SDM では，削除されるサブ

削除時の最近傍探索の実行回数や，ディスコードが変化する場

シーケンスの RL が大きい場合でもディスコードになり得ない

合に必要な最近傍探索の回数が変化するからである．

サブシーケンスに対しては最近傍探索を実行しないが，一方で，ディスコードが変化するとき，NN タプルを保持していな
いサブシーケンスに対して最近傍探索を実行する必要がある．

SDM

10

15

20

5

ウィンドウサイズ [×103]

SDM

2500
2000
1500

1000
500
0
10

15

20

5

15

20

I-SDM

2000
1500

1000
500
0
15

20

ウィンドウサイズ [×103](e) Google-CPU

10

SDM

2500

10

I-SDM

15

SDM

N-SDM

5

10

(f) Google-Memory

N-SDM

20

I-SDM

SDM

2000
1500

1000
500
0
15

20

(d) ECG

2500

10

15

ウィンドウサイズ [×103]

3000

5

I-SDM

160
140
120
100
80
60
40
20
0

(c) GreenHouseGas

3000

5

ウィンドウサイズ [×103]

N-SDM

N-SDM

ウィンドウサイズ [×103]

最悪更新時間 [msec]

I-SDM

3000

5

10

(b) Google-Memory

最悪更新時間 [msec]

最悪更新時間 [msec]

N-SDM

SDM
160
140
120
100
80
60
40
20
0

ウィンドウサイズ [×103](a) Google-CPU
SDM

I-SDM

最悪更新時間 [msec]

5

N-SDM

160
140
120
100
80
60
40
20
0

平均更新時間 [msec]

I-SDM

更新時間 [msec]

N-SDM

平均更新時間 [msec]

平均更新時間 [msec]

SDM
160
140
120
100
80
60
40
20
0

20

ウィンドウサイズ [×103](g) GreenHouseGas

N-SDM

I-SDM

3000
2500
2000
1500

1000
500
0
5

10

15

20

ウィンドウサイズ [×103](h) ECG

図 6: w の影響（(a)–(d)：平均更新時間，(e)–(h)：最悪更新時間）

6 結論

近年注目されている IoT 機器では，ストリーミング時系列
データを生成するため，時系列データをリアルタイムに解析することがより重要になっている．本稿では，ディスコード（時系列データの中で他と最も異なるサブシーケンス）をモニタリングする問題に初めて取り組んだ．効率的にディスコードをモ
ニタリングするため，SDM を提案した．SDM は，最近傍のサ
ブシーケンスおよび自身を最近傍とするサブシーケンスのリス
トを保持することにより，効率的にディスコードをモニタリン
グできる．4 つの実データを用いた実験により，SDM の有効性を確認した．
謝辞．本研究の一部は，基盤研究 (A)(JP18H04095)，基盤研
究 (B)(JP17KT0082)，および若手研究 (B)(JP16K16056) の研究助成によるものである．ここに記して謝意を表す．
文

献[1] Y. Chen, M.A. Nascimento, B.C. Ooi, and A.K. Tung,“Spade: On shape-based pattern detection in streaming
time series,” ICDE, pp.786–795, 2007.
[2] B. Chiu, E. Keogh, and S. Lonardi, “Probabilistic discoveryof time series motifs,” KDD, pp.493–498, 2003.
[3] T. Huang, Y. Zhu, Y. Mao, X. Li, M. Liu, Y. Wu, Y. Ha, and
G. Dobbie, “Parallel discord discovery,” PAKDD, pp.233–
244, 2016.
[4] S. Kato, D. Amagata, S. Nishio, and T. Hara, “Monitoring
range motif on streaming time-series,” DEXA, pp.251–266,
2018.
[5] E. Keogh, J. Lin, and A. Fu, “HOT SAX: Eﬃciently finding
the most unusual time series subsequence,” ICDM, pp.226–
233, 2005.
[6] H.T. Lam, N.D. Pham, and T. Calders, “Online discovery
of top-k similar motifs in time series data,” SDM, pp.1004–
1015, 2011.
[7] Y. Li, L. Zou, H. Zhang, and D. Zhao, “Computing longest
increasing subsequences over sequential data streams,”

PVLDB, vol.10, no.3, pp.181–192, 2016.
[8] D. Lucas, C.Y. Kwok, P. Cameron-Smith, H. Graven,
D. Bergmann, T. Guilderson, R. Weiss, and R. Keeling,“Designing optimal greenhouse gas observing networks thatconsider performance and cost,” Geoscientific Instrumentation, Methods and Data Systems, vol.4, no.1, p.121, 2015.
[9] M. Moshtaghi, C. Leckie, and J.C. Bezdek, “Online clustering of multivariate time-series,” SDM, pp.360–368, 2016.
[10] A. Mueen and E. Keogh, “Online discovery and maintenance of time series motifs,” KDD, pp.1089–1098, 2010.
[11] P. Patel, E. Keogh, J. Lin, and S. Lonardi, “Mining motifs
in massive time series databases,” ICDM, pp.370–377, 2002.
[12] C. Reiss, J. Wilkes, and J.L. Hellerstein, “Google clusterusage traces: format+ schema,” Google Inc., White Paper,
pp.1–14, 2011.
[13] H. Sanchez and B. Bustos, “Anomaly detection in streaming
time series based on bounding boxes,” SISAP, pp.201–213,
2014.
[14] D. Yankov, E. Keogh, and U. Rebbapragada, “Disk aware
discord discovery: Finding unusual time series in terabyte
sized datasets,” KIS, vol.17, no.2, pp.241–262, 2008.
[15] C.C.M. Yeh, Y. Zhu, L. Ulanova, N. Begum, Y. Ding, H.A.
Dau, D.F. Silva, A. Mueen, and E. Keogh, “Matrix profile i: all pairs similarity joins for time series: a unifying
view that includes motifs, discords and shapelets,” ICDM,
pp.1317–1322, 2016.