ダイナミックタイムワービング距離に基づくストリーム処理

摘要

近年，ノデータストリーム処理に関する研究が盛んに行われている．本論文は，ダイナミックタイrnムワービング（DTW：Dynamic Time Warping）に基づいて，与えられた問合せシーケンスと類似した部分rnシーケンスをデータストリームから検出することを目的とする．DTWは時間軸上でのスケーリングを考慮したrn距離尺度であり，様々な分野で広く使われているが，主として有限長の蓄積データに用いられてきた．しかし，rnネットワーク分析，センサ監視など，データ量が多く，緊急性が要求されるような最近のアプリケーションでrnは，すべてのデータを蓄積してから処理することが困難である．本論文では，このような問題を解決する手法rnであるSPRINGを提案する．更に理論的な分析を行い，精度を犠牲にしないにもかかわらず計算コストがデーrnタストリームの長さに依存せず一定であることを証明する．様々な実データと人工データを用いた実験を行い，rnSPRINGがデータストリームから正確に部分シーケンスを検出し，そしてナイーブな手法と比較して大幅な性rn能向上を達成していることを明らかにした．