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

書誌事項

タイトル別名
  • ブブン シーケンスマッチング ノ タメ ノ ストリーム アルゴリズム
  • A Stream Algorithm for Subsequence Matching

この論文をさがす

抄録

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

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (25)*注記

もっと見る

関連プロジェクト

もっと見る

詳細情報

問題の指摘

ページトップへ