講演内容

データストリームのための時系列処理

最近のデータストリーム処理の取り組み
タイムワーピング距離に基づくストリーム監視
Y. Sakurai, C. Faloutsos, M. Yamamuro:Stream Monitoring under the Time Warping Distance.
ICDE 2007
 データストリームにおける遅延相関の検出
Y. Sakurai, S. Papadimitriou and C. Faloutsos:
BRAID: Stream Mining through Group Lag Correlations.
SIGMOD Conference 2005: 599-610
櫻井 保志NTT サイバースペース研究所


その他，最近の興味など
2蓄積型とストリーム型


データストリーム処理

蓄積型の時系列データ処理

データストリームにおける問合せ処理
データを受信する毎にシーケンスは長くなる （膨大なデータ）
ディスクのアクセスは避ける,しかしメモリ使用量には制限
 ストリームの‘スケッチ’を作成，更新
 処理結果は（一般的に）近似

例：類似シーケンスの検索処理 あらかじめ時系列DBからインデックスを作成
 問合せにより類似したシーケンスを探索 検索結果は（一般的に）厳密

時系列データのインデックス

時系列DB

時系列データ
検索エンジン

ストリームのスケッチ

（厳密な）
検索結果

データストリーム

ストリーム処理
エンジン

（近似の）
処理結果

3

4

研究目的
タイムワーピング距離に基づく
ストリーム監視 データストリームのアプリケーション

ネットワーク分析
センサー監視 金融
 ムービングオブジェクト


 研究目的

データストリームをモニタリング
固定長の問合せシーケンスと類似した部分シーケンスを検出 距離基準：ダイナミックタイムワーピング (DTW)61

ダイナミックタイムワーピング(DTW)

ダイナミックタイムワーピング(DTW)

時間軸方向にシーケンス長を調整

シーケンス間の距離を最小化
 シーケンスに ‘stutter’ を挿入 その後，(ユークリッド) 距離を計算


DTWは動的計画法(dynamic programming)で計算
ワーピングパス：タイムワーピング行列の中のセルの集合
Optimum warping path(the best alignment)
Xxi

x1

yM
xN
x-stutters

Yyjy1

yM

yjYoriginal‘stutters’

y1
x1
y-stutters

xiXxN

タイムワーピング行列
7

DTWの定義

8

関連研究

二つのシーケンス X と Y が与えられたとき



DTWは動的計画法により計算
D ( X , Y ) = f ( n, m )⎧ f (t , i − 1)⎪f (t , i ) = xt − yi + min ⎨ f (t − 1, i )⎪ f (t − 1, i − 1)
⎩f (0,0) = 0, f (t ,0) = f (0, i ) = ∞シーケンスのインデックス，部分シーケンスマッチング
Agrawal et al. (FODO 1998)
Keogh et al. (SIGMOD 2001)
 Faloutsos et al. (SIGMOD 1994)
 Moon et al. (SIGMOD 2002)

X=(x1 , x2 ,…, xn) ; Y=( y1 , y2 ,…, ym )X-stutterY-stutterno stutter

DTWのためのシーケンスマッチング処理
Yi et al. (ICDE 1998)
Keogh (VLDB 2002)
 Zhu et al. (SIGMOD 2003)
 Sakurai et al. (PODS 2005)



910

問題定義

関連研究
データストリームのためのパターン検出
 データストリームのクラスタリング
Guha et al. (TKDE 2003)
 ストリームのモニタリング
Zhu et al. (VLDB 2002)
 情報予測Papadimitriou et al. (VLDB 2003)
 遅延相関
Sakurai et al. (SIGMOD 2005)
 従来研究の中で，ここで提起した問題を扱う研究はない

シーケンス X=(x1 , x2 ,…, xn)

問題1：ベストマッチ問合せ (Best-match query)
とり得る全ての X[t, i] の中で，Yからの距離が最小となる
X[ts,te] を検出
 全ての t=1,…,n と j=t,…,n について
D ( X [t s : te ], Y ) ≤ D ( X [t : j ], Y )11

固定長の問合せシーケンス Y から部分シーケンスX[ts,te] を検出

ベストマッチ問合せはストリーム型よりも蓄積型
範囲問合せの方がデータストリームの監視に適している122ダイナミックタイムワーピング(DTW)

部分シーケンスマッチング

DTWは動的計画法(dynamic programming)で計算



ワーピングパス：タイムワーピング行列の中のセルの集合
Optimum warping path(the best alignment)
X
xi

x1

xts

x1

X

xte

xnyM
xN
x-stutters

Yyjy1y1
x1

yM

yj
Y

y-stutters

xi
X

y1xN

Y

タイムワーピング行列

ym1314

部分シーケンスマッチング

問題定義

 データ受信毎にタイムワーピング行列を作成



データストリームのための部分シーケンスマッチング




Y

2重の害





x1
xt

X

範囲問合せ：距離が ε 以下の部分シーケンスを検出
極小値をとる X[ts:te] と重複する部分シーケンスが数多く存在
利用者に冗長な情報を与えて悩ませる
不必要な結果も報告させるために処理速度が低下

余分な部分シーケンスを除外

xt+l-1

標準的な範囲問合せ + 追加条件

15

部分シーケンスマッチング

16

問題定義


別の類似部分シーケンス

問題2：ディスジョイント問合せ (Disjoint query)閾値 ε として，二つの条件を満たす全ての X[ts:te] を検出
条件1: D ( X [t s : t e ], Y ) ≤ ε
 条件2: 極小値をとる部分シーケンス
条件1を満たし，かつ重複する部分シーケンスのグループの中で D ( X [t s : t e ], Y ) が最小
 ベストマッチ問合せと範囲問合せの組合せ
X

X[ts:te]

データストリーム監視のために

‘最適な’部分シーケンスを可能な限り早く出力

Y
17183

ナイーブな方法

ナイーブな方法 Super-Naïve

O(n) 個のタイムワーピング行列

全ての部分シーケンス X [t s : te ] (1 ≤ t s ≤ te ≤ n)を考えて動的計画法を適用
 全ての計算量は O(n3m)，1レコード受信あたり O(n2m) O(n2) のタイムワーピング行列
Yx1

 Naïve

xt+l-1xt

開始点が同じである部分シーケンスは行列を共有
 1レコード受信あたり O(nm) の計算量
 O(n) のタイムワーピング行列

ディスジョイント問合せX
全ての部分シーケンスの距離を計算し，重複するものの中から最適な部分シーケンスを出力

1920

SPRING

提案手法SPRING

Report X[ts:te] アイデア1: スターパディング (Star-padding)

1つの行列を用いて処理 (ナイーブな手法はm個)常に距離0を示す値 ’＊’ を Y に添える
 Y=(y1, y2, …, ym) の代わりにY’を用いて距離計算
Y’=(y0, y1, y2, …, ym)
y0 = (-infinity, +infinity) O(m) の計算量とメモリ使用量（ナイーブはO(nm) ）Report the 2ndsubsequenceY′
t=1 t=tst=te

X
21

提案手法SPRING
アルゴリズム

アイデア2：拡張タイムワーピング行列

スターパディングの問題
 最適な部分シーケンスの位置情報を失ってしまう スキャンの後，どの部分シーケンスが最小距離を出力したの？


拡張タイムワーピング行列

部分シーケンスの距離値
その部分シーケンスの開始点

スターパディングとの組合せによるストリーム処理

22

不要な部分シーケンスを除去
最小距離を示す部分シーケンスの位置を認識
23

ディスジョイント問合せ
データ1つ受信する毎に行列のm個の要素（距離，開始点）を更新 ε 以下の部分シーケンスを検出すると，最適な部分シーケンスかどうかチェック (a)(b)の条件を満たすときに現在の最適な部分シーケンスを出力(a) これから出現する候補部分シーケンスは最適でない(b) これから出現する候補部分シーケンスは現在の最適部分シーケンスと重複しない


24

4

SPRINGの例

実験

 上の値：距離，括弧内の値：開始点
 X=(5,12,6,10,6,5,13)

 実データと人工データを用いて実験

Y=(11,6,9,4)

 3つの評価項目

シーケンスのパターン検出はうまくいくのか？
シーケンス長 n が伸びると計算時間とメモリ量はどうなる？
 ディスジョイント問合せについて，二つの提案手法に動作の違いはあるのか？


25

26

パターン検出パターン検出 類似パターンをストリームから検出 類似パターンをストリームから検出

MaskedChirp

問合せシーケンス



データストリーム

MaskedChirp

問合せシーケンス

データストリーム27

28

パターン検出パターン検出 類似パターンをストリームから検出 類似パターンをストリームから検出Temperature

問合せシーケンス



データストリーム

Temperature

問合せシーケンス

29

データストリーム

30

5パターン検出

パターン検出 類似パターンをストリームから検出 類似パターンをストリームから検出Sunspots

問合せシーケンス



データストリーム

Sunspots

問合せシーケンス

データストリーム

31

32

パターン検出パターン検出 類似パターンをストリームから検出 類似パターンをストリームから検出



Kursk

問合せシーケンス



データストリーム

Kursk

問合せシーケンス

データストリーム

33

34

パターン検出パターン検出 類似パターンをストリームから検出 類似パターンをストリームから検出

Automobile

問合せシーケンス



データストリーム

Automobile

問合せシーケンス

35

データストリーム36

6

パターン検出

パターン検出 類似パターンをストリームから検出 類似パターンをストリームから検出Humidity

問合せシーケンス



データストリーム

Humidity

問合せシーケンス

データストリーム

37

38

処理時間

メモリ使用量 1レコードあたりの処理時間

タイムワーピング行列のためのメモリ使用量
ナイーブな手法はO(nm)SPRINGはO(m)，シーケンス長nに依存しない
 ワーピングパスに関する情報を出力する場合でも省メモリ化を達成

ナイーブな手法はO(nm)提案手法はO(m)，シーケンス長nに依存しない




39

提案アルゴリズムの比較

提案アルゴリズムの比較

閾値ε を変化40



SPRING-optimal

閾値ε を変化

SPRING-firstε = 10,000

ε = 10,000

問合せシーケンス

問合せシーケンス

ε = 15,000

ε = 15,000
41427

パターン認識とストリーム技術の融合

映像処理への応用

 データストリーム処理技術の映像への応用
 パターン検出の例


人物にセンサーを取り付け （カーネギーメロン大学）
運動量の類似性をもとにして動作を検出

Erotation =

1 2Iω
2

Erotation: 角運動量, I: 慣性モーメント, ω: 角速度


娯楽のためのアプリケーション
リアルタイム映像作成
43

動作の高速な認識44

まとめ

データストリームに含まれる動作

SPRING: DTWに基づくデータストリームのための部分シーケンスマッチング
高速，省メモリ




Walk

Swing

RotateSwing

Rotate

精度





Jump

Walk

Run

検出漏れがないことを保証

蓄積型への適用も可能

One-leg jump

O(m) の計算時間とメモリ空間，n に依存しない蓄積型の検索手法と組み合わせることが可能

Walk

45

46

研究目的

データストリームにおける遅延相関の検出

 データストリームのアプリケーション

ネットワーク分析
センサー監視 金融
 ムービングオブジェクト
 研究目的

複数のストリームをモニタリング
どのペアに遅延相関があるのかを検出
 遅延の値を報告（もし相関しているペアがあれば）


488

遅延相関

遅延相関
 遅延相関のあるシーケンス

 遅延相関の例

遅延 l=1300 でこれらのシーケンスは相関している



金利が下がると数ヵ月後に住宅着工数が増加する



水道水にフッ素を多く混入させると数年後に虫歯の患者数が減少する



サーバー1のCPUの利用率が上昇すると数分後にサーバー2のCPU利用率も上昇する

CCF (Cross-Correlation Function)4950

問題1： シーケンスのペア

遅延相関
 遅延相関のあるシーケンス

高速 省メモリ
 高精度


伸長するシーケンス XとY について，


遅延相関があるかどうか
もし遅延相関があれば，遅延の長さ l はどれくらいかを推定する（少ない誤差）X?

yes;
l = 1,300Y


CCF (Cross-Correlation Function)

データストリーム（伸長するシーケンス）において，いつでも報告可能51

提案手法，BRAID

問題2： k-way 与えられた k 個のシーケンス X1,…,Xk について 特徴

どのペアに遅延相関があるのか そのペア各々の遅延の値を推定する
X1?

X2

52



いつでも処理可能，そして高速

省メモリ

単位時間あたりの計算時間は一定
メモリ空間は，シーケンス長 n に対して O(log n)

X1 and X2; l = 1,300...

...

高精度
近似誤差は小さいXk

いつでも，ストリーム上で．．．
53

549

関連研究

関連研究

 シーケンスのインデックス

 データストリーム管理

Agrawal et al. (FODO 1993) Faloutsos et al. (SIGMOD 1994)
 Keogh et al. (SIGMOD 2001)


Abadi et al. (VLDB Journal 2003)
Motwani et al. (CIDR 2003)
 Chandrasekaran et al. (CIDR 2003)
 Cranor et al. (SIGMOD 2003) データ圧縮 （ウェーブレット変換，ランダム射影）

Gilbert et al. (VLDB 2001)
Guha et al. (VLDB 2004)
 Dobra et al.(SIGMOD 2002)
 Ganguly et al.(SIGMOD 2003)


55

関連研究




56

アウトライン

パターン検出 データストリームのクラスタリング
Guha et al. (TKDE 2003)
 ストリームのモニタリング
Zhu et al. (VLDB 2002)
 情報予測Yi et al. (ICDE 2000)
Papadimitriou et al. (VLDB 2003)

 研究目的，関連研究
 前提条件 提案手法 理論的な分析 実験結果従来研究の中で，ここで提起した問題を扱う研究はない
57

前提条件

58

前提条件

details ‘score’の定義，R(l) の絶対値

 遅延相関相関score(l ) = R (l )R (l ) =無相関

Correlation+γ

反相関(-γ より低い値)∑nt =l +1∑n( xt − x )( yt −l − y )( xt − x ) 2t =l +1∑ ( y − y)n −lt =12t

 遅延相関

しきい値 γ が与えられたとき，score(l ) > γ
local maximum （極大値）
 遅延が最も少ない local maximumLag
CCF (Cross-Correlation Function)
59

60

10

アウトラインナイーブな方法
 高速化手法を使わない場合

 研究目的，関連研究

 前提条件 提案手法各々の遅延について相関係数を計算
l = 0, 1, 2, 3, …, n/2 実験結果メモリ空間 O(n)計算時間 O(n2)もしくは O(n log n) w/ FFTCorrelation

 しかし 理論的な分析

t=nTime0Lag61

“the correlation coefficient of two sequences is‘algebraic’” => 相関値はインクリメンタルに計算可能

details Incremental computing: インクリメンタルな計算
62

Main Idea (1)アイデア（１）

n/2

Sequence length nn
Sx(1, n) = ∑t =1 xt
Sum of X :nSxx(1,n)=
Square sum of X :∑t =1 xt2nInner-product for X and the shifted Y : Sxy (l ) = ∑t =l +1 xt yt −lCompute R(l) incrementally:

6つの基本統計情報，‘sufficient statistics’

R (l ) =シーケンス長 n シーケンス X の和，X の2乗和 シーケンス Y の和，Y の2乗和
 X と シフトしたY の内積C (l )
Vx(l + 1, n) ⋅Vy (1, n − l )Covariance of X and Y:

Variance of X:

Sx(l + 1, n) ⋅ Sy (1, n − l )n−l( Sx (l + 1, n)) 2
Vx(l + 1, n) = Sxx(l + 1, n) −n−lC (l ) = Sxy(l ) −6364

アイデア（１）

アイデア（２）

 計算量

 等比数列に基づくCCFのサンプリング

Naive(incremental)

空間計算量

O(n)

O(n)

時間計算量

O(n log n)

O(n)

BRAID
Correlation

Naiveもっと良くならない？

Lag65

66

11アイデア（２）アイデア（２）

 等比数列に基づくCCFのサンプリング 等比数列に基づくCCFのサンプリング 遅延

l = 0, 1, 2, 4, ... 2hについて，相関係数をNaive
空間計算量

O(n)

Naive(incremental)
O(n)

時間計算量

O(n log n)O(n)O(log n) estimations

Correlation

計算BRAID

O(log n) 例えば遅延の最大値を n/2 とすると，O(n) の0 1 24
Lag8

メモリが必要67

68

アイデア（３）

アイデア（３）

 シーケンスの平滑化

 シーケンスの平滑化

各レベルの窓の平均
基本統計情報は平均値から計算
 遅延相関は平均値の基本統計情報から計算
 しかし，冗長な情報がある …
Time

Correlation

ナイーブな方法

Levelt=nTimeh=0t=nCorrelationLag

Lag
69

70

アイデア（２）と（３）アイデア（２）と（３） サンプリング + 平滑化

 サンプリング + 平滑化

カラーで示した窓のみを使う
等比数列の遅延のみ計算
l={0,1,2,4,8,…,2h,…}

Level

Time

h=0t=n

カラーで示した窓のみを使う
等比数列の遅延のみ計算
l={0,1,2,4,8,…,2h,…}
Y

h=0
l=0

Level

XTime
Lag

h=0t=nCorrelation



Correlation



Lag
71

72

12

アイデア（２）と（３）

アイデア（２）と（３） サンプリング + 平滑化

 サンプリング + 平滑化

h=0
l=1

Level

X
Time

h=0t=n

カラーで示した窓のみを使う
等比数列の遅延のみ計算
l={0,1,2,4,8,…,2h,…}
YCorrelationY

h=1
l=2Correlation

カラーで示した窓のみを使う
 等比数列の遅延のみ計算
l={0,1,2,4,8,…,2h,…}LevelXTime

h=1
th=n/2Lag

Lag
7374

アイデア（２）と（３）

アイデア（２）と（３） サンプリング + 平滑化

 サンプリング + 平滑化

h=2
l=4LevelX

h=2Time

カラーで示した窓のみを使う
等比数列の遅延のみ計算
l={0,1,2,4,8,…,2h,…}
YCorrelation

Y



h=3
l=8LevelX

th=n/4h=3TimeCorrelation

カラーで示した窓のみを使う
 等比数列の遅延のみ計算
l={0,1,2,4,8,…,2h,…}

th=n/8Lag

Lag
7576

結果として…

アイデア（２）と（３） サンプリング + 平滑化

 計算量

カラーで示した窓のみを使う
 等比数列の遅延のみ計算l={0,1,2,4,8,…,2h,…} 3次元スプラインを用いて相関値を補間Time

h=0t=nCorrelation

Level

Naive
空間計算量

O(n)

Naive(incremental)
O(n)

時間計算量

O(n log n)

O(n)

BRAID
O(log n)O(1) *(*) 時間計算量 O(log n)ならし計算量 O(1)
Lag
77

78

13

アウトライン

精度の向上

 研究目的，関連研究Q: どうすれば 2h よりも細かくサンプリングできる？

 前提条件 提案手法

提案手法の発展 実験結果Level
h=0t=nTimeCorrelation

 理論的な分析

Lag
79

80

精度の向上

Enhanced BRAID

Q: どうすれば 2h よりも細かくサンプリングできる？
 A: 等比数列と等差数列の併用



基本スキームは b=1 （各レベルに一つ）
改良スキームは b>1


Level

Time

h=0t=nb=4 の例
等比数列と等差数列を併用したCCFのサンプリング
l={0,1,…,7;8,10,12,14;16,20,24,28;32,40,…}

Correlation



Level
h=0Correlation



step:1

step: 2

step: 4t=nTime
Lag

Lag
81

アウトラインdetails 研究目的，関連研究

82

理論的な分析 – 精度

details

 平滑化の効果

 前提条件

低周波で構成されたシーケンスに対しては，平滑化による誤差は小さい

 提案手法 理論的な分析 サンプリングの効果 実験結果標本化定理（ナイキスト）を満たすとき，BRAIDは誤差を生まない

83

84

14

理論的な分析 – 精度
details

サンプリングの効果

理論的な分析 – 計算量メモリ空間 O(n)BRAID
 メモリ空間 O(log n)

時間 O(n)

統計値の更新のための時間 O(1)

補間のための時間O(log n)（アウトプットを要求されたとき）

Naive solution

概要：標本化定理（ナイキスト）を満たすとき，BRAIDは誤差を生まない 詳細：details

以下を満たすとき，BRAIDは必ず遅延相関を見つけることができる
2b0≤l ≤fR
fR: CCFのナイキスト周波数, fR=min(fx, fy)
fx, fy: X と Y のナイキスト周波数8586

アウトライン

実験結果

 研究目的，関連研究

 設定

 前提条件 提案手法Intel Xeon 2.8GHz, 1GB memory, Linux
データ
人工データ Sines, SpikeTrains,
実データ Humidity, Light, Temperature, Kursk,
Sunspots Enhanced BRAID, b=16

 理論的な分析 実験結果87

CCFの近似（１）88

CCFの近似（２） Sines SpikeTrains
BRAID は，遅延係数を高精度に近似

BRAID は，遅延係数を高精度に近似

CCF (Cross-Correlation Function)

CCF (Cross-Correlation Function)
89

90

15

CCFの近似（３）CCFの近似（４） Humidity (実データ)

 Light (実データ)
BRAID は，遅延係数を高精度に近似

BRAID は，遅延係数を高精度に近似

CCF (Cross-Correlation Function)

CCF (Cross-Correlation Function)
91

CCFの近似（５）92

CCFの近似（６） Kursk (実データ)

 Sunspots (実データ)
BRAID は，遅延係数を高精度に近似

BRAIDの遅延相関の近似誤差は小さい

CCF (Cross-Correlation Function)

CCF (Cross-Correlation Function)93

遅延相関の近似誤差
Datasets94

計算時間

Lag correlation Estimation
Naive BRAID error (%)

Sines

716

716

0.000

SpikeTrains

2841

2830

0.387

Humidity

3842

3855

0.338

Light

567

570

0.529

Kursk

1463

1472

0.615

Sunspots

1156

1168

1.038

 大幅に計算時間を削減

 相対誤差の最大値は約1%

 最大で 約40,000 倍の高速化
95

9616

理論的な分析 – 精度

複数ペアの遅延相関Temperature，シーケンス数55

相関のある二つのペア



details

サンプリングの効果
概要：標本化定理（ナイキスト）を満たすとき，BRAIDは誤差を生まない
 詳細：
#16

#19

Estimation of CCF of #16 and #19

#47

#48

Estimation of CCF of #47 and #48

以下を満たすとき，BRAIDは必ず遅延相関を見つけることができる
2b0≤l ≤fR
fR: CCFのナイキスト周波数, fR=min(fx, fy)
fx, fy: X と Y のナイキスト周波数97

CCFの近似（１）98

サンプリングの効果

 Sinesdetails データ： Sines

BRAID は，遅延係数を高精度に近似

 基本スキーム b=1
 lR=1024

CCF (Cross-Correlation Function)
99

CCFの近似（４）100

サンプリングの効果

 Light (実データ)

details データ： Light
BRAID は，遅延係数を高精度に近似

 基本スキーム b=1
 lR=630

CCF (Cross-Correlation Function)
101

102

17

まとめ

データストリームのための遅延相関検出
1. いつでも処理可能
2. 省メモリ

統計情報の更新にO(log n) のメモリ空間，O(1) の時間

3. 高速

ナイーブな実装と比べて，40,000 倍の高速化

4. 高精度相対誤差の最大値は約1%10318