部分シーケンスマッチングのためのストリームアルゴリズム

摘要

あらまし　本論文では，データストリームにおけるcross－Similarityの問題を定義する．本論文の目的は，データストリームから類似する部分シーケンスペアを検出することである．シーケンス間の類似度を測定する距離尺度には，時間軸上でのスケーリングを考慮することができるダイナミックタイムワービング（DTW：Dynamic Time Warping）距離を利用する．我々の提案するCrossMatchは，厳密にDTWに基づいた手法であり，データストリーム処理に適したワンパスアルゴリズムである．DTWを用いた純粋なアルゴT）ズムと比べて，CrossMatchは計算コストとメモリ使用量の大幅な低減化を実現する．理論的な分析を行い，提案アルゴリズムが精度を犠牲にすることなく類似する部分シーケンスペアを検出することを示す．また，実データと人工データを用いた実験から，CrossMatchがインクリメンタルにcross－Similarityを検出することが確認された．