- 著者
-
櫻井 保志
Christos Faloutsos
山室 雅司
- 出版者
- The Institute of Electronics, Information and Communication Engineers
- 雑誌
- 電子情報通信学会論文誌 D (ISSN:18804535)
- 巻号頁・発行日
- vol.J92-D, no.3, pp.338-350, 2009-03-01
近年,データストリーム処理に関する研究が盛んに行われている.本論文は,ダイナミックタイムワーピング(DTW:Dynamic Time Warping)に基づいて,与えられた問合せシーケンスと類似した部分シーケンスをデータストリームから検出することを目的とする.DTWは時間軸上でのスケーリングを考慮した距離尺度であり,様々な分野で広く使われているが,主として有限長の蓄積データに用いられてきた.しかし,ネットワーク分析,センサ監視など,データ量が多く,緊急性が要求されるような最近のアプリケーションでは,すべてのデータを蓄積してから処理することが困難である.本論文では,このような問題を解決する手法であるSPRINGを提案する.更に理論的な分析を行い,精度を犠牲にしないにもかかわらず計算コストがデータストリームの長さに依存せず一定であることを証明する.様々な実データと人工データを用いた実験を行い,SPRINGがデータストリームから正確に部分シーケンスを検出し,そしてナイーブな手法と比較して大幅な性能向上を達成していることを明らかにした.