ダイナミックプログラミングに基づくストリームマッチング(セッション7b:ストリーム・スカイライン)
スポンサーリンク
概要
- 論文の詳細を見る
データストリームはさまざまな分野で発生するデータであり,これらのデータの処理が重要となっている.本稿では,ダイナミックプログラミングに基づいて,データストリームから類似する部分シーケンスのペアを検出する問題に焦点を当てる.ストリームのサンプリングレートの違いや周期の変化を考慮した場合,時間スケールを扱う距離尺度が必要となる.従来,時間スケールを扱う距離尺度としてダイナミックタイムワーピング(DTW:Dynamic Time Warping)が用いられてきたが,主に蓄積されたデータを対象としているため,ストリーム処理に適用した場合に大幅な計算コストを必要とする.本稿では,データストリームにおける類似度を測定するために,新たな距離尺度を提案し,それを用いた効率的なアルゴリズムを示す,実データと人工データを用いた実験では,従来手法と比較して,大幅な性能向上を達成していることが確認された.
- 2008-09-14
著者
-
櫻井 保志
日本電信電話株式会社NTTサイバースペース研究所
-
櫻井 保志
Nttコミュニケーション科学基礎研究所
-
櫻井 保志
日本電信電話(株)nttサイバースペース研究所
-
豊田 真智子
日本電信電話株式会社NTT情報流通プラットフォーム研究所
-
市川 俊一
日本電信電話株式会社NTT情報流通プラットフォーム研究所
-
市川 俊一
NTT情報流通プラットフォーム研究所
-
豊田 真智子
NTTコミュニケーション科学基礎研究所
-
豊田 真智子
日本電信電話株式会社nttコミュニケーション科学基礎研究所:名古屋大学大学院情報科学研究科
-
豊田 真智子
日本電信電話株式会社nttコミュニケーション科学基礎研究所
関連論文
- ダイナミックタイムワーピング距離に基づくストリーム処理(パターン照合・パターン発見,データ工学論文)
- ダイナミックプログラミングに基づくストリームマッチング(セッション7b:ストリーム・スカイライン)
- SPIRAL : 隠れマルコフモデルのための高速探索手法(ポスターセッション,iDBフォーラム2008(招待講演・ポスター英語ディスカッション))
- XML木のための動的範囲ラベル付け手法
- 隠れマルコフモデルデータベースの高速ゆう度検索(データ工学研究専門委員会推薦論文,空間データベース,データ工学論文)
- 楕円体問合せのための空間変換を用いた類似探索アルゴリズム
- 楕円体問合せのための類似探索手法の提案
- 高次元データのための相対的近似を用いた索引手法
- 多次元空間における類似探索手法の提案
- 階層的センサネットワークのための効率的なデータ収集手法
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- ユビキタスセンサを用いたライフログの蓄積と利用(セッション2)
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- 低周波振動の伝播を利用した屋内での作業道具の位置検出手法
- 実世界イベント理解に向けた語彙集合の構築と評価
- センサネットワークのためのトポロジーの変化を考慮したデータ集約方式(セッション3:慶應義塾大学)
- 高密度なセンサネットワークにおけるデータ収集のための階層的クラスタリング手法の提案(企画:「シミュレーションと現実のギャップを埋められるのか?」,モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- BS-14-3 センサ情報からの実世界言語化・可視化・コンテンツ化(BS-14.ユビキタス・センサーネットワーク技術〜モノによるユビキタス環境を目指して〜,シンポジウムセッション)
- 振動波と加速度センサを用いた物体間の接触関係の取得手法(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- 振動波と加速度センサを用いた物体間の接触関係の取得手法(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- センサデータ解釈のための拡張可能な知識構築手法(第3セッション)
- 大規模センサネットワークにおける遅延の抑制を考慮したデータ収集機構の提案(UBI-3【センサネットワーク/実世界センシング】)
- 大規模センサネットワークにおける遅延の抑制を考慮したデータ収集機構の提案(UBI-3【センサネットワーク/実世界センシング】)
- 小型無線デバイスとセンサデータを用いた物体間の相対的な位置関係の推定
- タイムワーピングを考慮したトレンド検出(夏のデータベースワークショップ2007(データ工学,一般))
- タイムワーピングを考慮したトレンド検出(マイニング,夏のデータベースワークショップ2007(データ工学,一般))
- 大量データストリームの類似探索手法
- ウェアラブルセンサによるモノを用いた行動の認識について
- 2K-3 隠れマルコフモデルによるデータストリームのモニタリング手法(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 時系列データのためのストリームマイニング技術
- 大量頻度分布データのための高速探索アルゴリズム
- ダイナミックタイムワーピングのための類似探索手法
- 楕円体問合せのための類似探索手法の提案
- 仮想包囲矩形に基づく多次元データ集合に対する近傍探索
- ビットコーディングを用いたR-treeに基づく多次元空間内近傍探索の高速化
- 4.ストレージセントリックネットワーク技術(大容量化が進むストレージ技術)
- iSCSIを利用したシンクライアントPCシステムSTRAGEX(インターネットシステム)
- B-7-84 Ethernet over GRE方式を用いたマルチホップ性能評価(B-7.情報ネットワーク,一般セッション)
- s-room: 実世界リアルタイムコンテンツ化 : モノとコトに関する情報の生成とそのコンテンツ化(ユビキタス・センサネットワークを支える理論,および一般)
- B-19-12 ブログ・コミュニティ活性化のための記事連携方式の提案(B-19. ネットワークソフトウェア,一般セッション)
- 部分シーケンスマッチングのためのストリームアルゴリズム
- 階層的センサネットワークのための特異値分解を用いたデータ圧縮手法 (ユビキタス・センサネットワーク)
- 部分シーケンスマッチングのためのストリームアルゴリズム(データ工学,Web情報システム)
- 端末操作ログを対象にした情報漏洩につながる危険行動高速抽出方式(ライフログ,ライフログ活用技術,オフィスインフォメーションシステム,ライフインテリジェンス,一般)
- 日常物の利用情報を用いたコンテキストサーチ
- 階層的センサネットワークのための特異値分解を用いたデータ圧縮手法(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- 相関性のあるデータを集約する無線センサネットワークにおけるシンクノード決定問題の近似解法
- D-4-1 連鎖ネットワークRAIDの提案と分散バックアップへの適用(D-4. データ工学)
- 端末操作ログからの情報漏えい検出 (データベース Vol.4 No.4)
- データストリームにおける効率的なパターン検出
- データストリームにおける効率的なパターン検出
- 情報拡散過程のダイナミクス:非線形モデルの提案と情報予測
- 大規模Webクリックデータのためのイベント予測
- 手首に装着したカメラ付きセンサデバイスを用いた行動認識手法(モバイルコンピューティング,ユビキタス・センサネットワークを支えるシステム開発論文)
- 乾電池を模したセンサノードによる携帯型電化製品の利用の認識について(モバイルアドホックネットワーク,モバイル時代を支える次世代無線技術,フィールドセンシング及び一般)
- 振動波と加速度センサを用いた物体間の接触関係の取得手法
- 手首に装着したカメラ付きセンサデバイスを用いた行動認識手法
- 乾電池を模したセンサノードによる携帯型電化製品の利用の認識について