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

• 豊田, 真智子

• 櫻井, 保志

• 石川, 佳治

• TOYODA, Machiko

• SAKURAI, Yasushi

• ISHIKAWA, Yoshiharu

Bibliographic Information

Other Title

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

Abstract

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

Journal

• 電子情報通信学会論文誌. D, 情報・システム

  電子情報通信学会論文誌. D, 情報・システム J94-D (7), 1058-1070, 2011-07

  一般社団法人電子情報通信学会

Keywords

• データストリーム
• 部分シーケンスマッチング
• ダイナミックタイムワーピング

Details

• CRID: 1050564288758104576
• NII Article ID: 110008672949
• NII Book ID: AA12099634
• HANDLE: 2237/23569
• NDL BIB ID: 11171341
• ISSN: 18804535
• Web Site: https://nagoya.repo.nii.ac.jp/records/21436
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I11171341
• Text Lang: ja
• Article Type: journal article
• Data Source:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN