ダイナミックプログラミングに基づくストリームマッチング

• Item type: SIG Technical Reports(1)
• 公開日: 2008-09-14
• タイトル: ダイナミックプログラミングに基づくストリームマッチング
• タイトル / 言語: en
• タイトル: Stream Matching based on Dynamic Programming
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本電信電話株式会社NTT情報流通プラットフォーム研究所
• 著者所属: 日本電信電話株式会社NTTコミュニケーション科学基礎研究所
• 著者所属: 日本電信電話株式会社NTT情報流通プラットフォーム研究所
• 著者所属(英): en
• 著者所属(英): NTT Information Sharing Platform Laboratories, NTT Corpration
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corpration
• 著者所属(英): en
• 著者所属(英): NTT Information Sharing Platform Laboratories, NTT Corpration
• 著者名: 豊田, 真智子; 櫻井, 保志; 市川, 俊一
• 著者名(英): Machiko, Toyoda; Yasushi, Sakurai; Toshikazu, Ichikawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: データストリームはさまざまな分野で発生するデータであり，これらのデータの処理が重要となっている．本稿では，ダイナミックプログラミングに基づいて，データストリームから類似する部分シーケンスのペアを検出する問題に焦点を当てる．ストリームのサンプリングレートの違いや周期の変化を考慮した場合，時間スケールを扱う距離尺度が必要となる．従来，時間スケールを扱う距離尺度としてダイナミックタイムワーピング (DTW: Dynamic Time Warping) が用いられてきたが，主に蓄積されたデータを対象としているため，ストリーム処理に適用した場合に大幅な計算コストを必要とする．本稿では，データストリームにおける類似度を測定するために，新たな距離尺度を提案し，それを用いた効率的なアルゴリズムを示す．実データと人工データを用いた実験では，従来手法と比較して，大幅な性能向上を達成していることが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Data stream are generated in several domain, and the processing is becoming increasingly important. In this paper, we focus on the problem of finding pairs of similar subsequences from data streams based on dynamic programming. Consider the difference of streams sampling rates and the variation of time period, a similarity measure which addresses time-scaling is important. DTW is a popular similarity measure and can consider time-scaling. However, since it have used for stored data set, it requires drastic time for data streams. In this paper, we propose a similarity method to measure similarity on data streams, and show an efficient algorithm with the similarity method. Our experiments on real and synthetic data sets demonstrated that our method is dramatically faster than the existing method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2008, 号 88(2008-DBS-146), p. 277-282, 発行日 2008-09-14
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会