SENSOR_FRAME
4.5. センサデータの時系列処理方式
本節ではKRAFTがQ時系列処理を解決することを示す．
4.5.1. 設計
Q時系列処理を解決するために，KRAFTのセンサ型は類似シーケンス検索を許す．セ ンサ型はDisteuclid(SA, SB)もDistdtw(SA, SB)も許す．KRAFTはSQLのサブセット を拡張して，類似検索を行う．
例えば，“(1,2,3)”に類似した，距離尺度が
Disteuclid(SA, SB) < 10 であり，表の名前がRobovieで，属性名がsonar1のセンサ
データシーケンスを検索するには，以下のように記述すればよい．
¶ ³
select ∗ from Robovie where simseq external Robovie.sonar1 [1,2,3] with euclid <10.
µ ´
このクエリでは，simseq externalは“外部シーケンスと類似したシーケンスを 検索せよ”を意味する．with euclidは “ 距離尺度をDisteuclid(SA, SB)にせよ”を 意味する．もしもeuclidがdtwと記述されていれば，距離尺度をDistdtw(SA, SB) にすることを意味する．
また，externalはinternalやlatestに変えることもできる．internalは内部 シーケンスとの比較を表し，latestは最新シーケンスとの比較を表す．
内部シーケンスとの比較は次のように行う．
¶ ³
select * from Robovie where simseq internal Robovie.sonar1[1][0,0][1081238444,0] with euclid = 0
µ ´
Robovie.sonar1[1][0,0][1081238444,0]の意味は，“IDが1で，比較元シーケン スはUNIX時間で0秒0µ秒から，1081238444秒0µ秒”である．
最新シーケンスとの比較は次のように行う．
¶ ³
select * from Robovie wheresimseq latest 10 item ofRobovie.sonar1[1] with euclid = 0
µ ´
simseq latest 10 item ofの意味は，“最新の10個のオブジェクトから構成され るシーケンスを比較元として類似検索を行う”である．これをsimseq latest 10s ofと変更すれば，“最新10秒間のオブジェクトから構成されるシーケンスを比較元 として類似検索を行う”になる．
4.5.1.0.4. 検索アルゴリズム 類似シーケンス検索アルゴリズムを図4.32に示
す．このアルゴリズムはbrute force方式である．すなわちスライディングウィン ドウを先頭から終端まで移動させていく間に，ユーザが指定した条件を満たす窓が あれば，それを答え返却用リストに追加していく．1行目でウインドウがセットさ れる．2行目から7行目において検索処理が実行される．
索引が準備されていないために検索コストが高い．それゆえ今後は索引もしくは 何らかの高速検索手法が実装される必要があろう．
¶ ³
1: Set W(Q);
2: for (i:= 0; i < M; i++) {
3: Calculate d using W(Q) and W(Si);
4: if (d meets condition(e.g, =0, <10, etc.)) { 5: Creates a new SENSOR SEGMENT;
6: Copies W(Si) to it;
7: } 8: }
µ ´
Q: Query sequence of length n
S: Sequence in database constituted of M elements Si: Subsequence of S startingi-th element of length n d: Distance betweenQ and Si
W: Window forQ orSi
図 4.32: サブシーケンス検索アルゴリズム
4.5.2. センサデータの時系列処理に関する評価
我々は，KRAFTへの類似シーケンス検索例を3つ示す．
• select sonar1 from robovie
→ {100,110,120,130,100,170}
• select sonar1 from robovie where simseq external [100,100,100] with euclid <10
→ {100,110,120}
• select sonar1 from robovie where simseq external [100,100,100] with dtw < 10
→ {100,110,120}{110,120,130}{120,130,100}
これらのサンプルクエリに関するDisteuclidとDistdtwを表4.4に示す．この結果よ り，DisteuclidはDistdtwよりも堅い尺度であることがわかる．
これらの実行結果より，KRAFTがDisteuclidとDistdtwのいずれの距離尺度も許す 類似検索を実行できると我々は主張する．それゆえKRAFTは問題2を解決する．
なお実行時間は，アルゴリズムがbrute forceであるから長い．それゆえ索引や 並列化による高速化が今後の課題である．
表 4.4: サンプルクエリへのDisteuclidとDistdtw Subsequences
Disteuclid Distdtw in database
{100,110,120} 7.45 4.47 {110,120,130} 12.5 8.00 {120,130,100} 12.0 9.17 {130,100,170} 25.4 17.4
4.5.3. まとめ
本節ではサンプルクエリを示しながら，KRAFTがQ時系列処理を解決することを示 した．検索処理の高速化が今後の課題である．