ダイナミックタイムワーピング距離に基づくストリーム処理(パターン照合・パターン発見,<特集>データ工学論文)
スポンサーリンク
概要
- 論文の詳細を見る
近年,データストリーム処理に関する研究が盛んに行われている.本論文は,ダイナミックタイムワーピング(DTW: Dynamic Time Warping)に基づいて,与えられた問合せシーケンスと類似した部分シーケンスをデータストリームから検出することを目的とする. DTWは時間軸上でのスケーリングを考慮した距離尺度であり,様々な分野で広く使われているが,主として有限長の蓄積データに用いられてきた.しかし,ネットワーク分析,センサ監視など,データ量が多く,緊急性が要求されるような最近のアプリケーションでは,すべてのデータを蓄積してから処理することが困難である.本論文では,このような問題を解決する手法であるSPRINGを提案する.更に理論的な分析を行い,精度を犠牲にしないにもかかわらず計算コストがデータストリームの長さに依存せず一定であることを証明する.様々な実データと人工データを用いた実験を行い, SPRINGがデータストリームから正確に部分シーケンスを検出し,そしてナイーブな手法と比較して大幅な性能向上を達成していることを明らかにした.
- 2009-03-01
著者
-
山室 雅司
日本電信電話株式会社NTTサイバースペース研究所
-
櫻井 保志
日本電信電話株式会社NTTサイバースペース研究所
-
櫻井 保志
日本電信電話株式会社nttコミュニケーション科学基礎研究所
-
櫻井 保志
日本電信電話(株)nttサイバースペース研究所
-
Faloutsos Christos
カーネギーメロン大学
-
山室 雅司
Ntt サイバースペース研
-
山室 雅司
日本電信電話株式会社 サイバースペース研究所
関連論文
- Folksonomyのタグを用いた自動分類体系構築へ向けて(夏のデータベースワークショップ2007(データ工学,一般))
- Folksonomyのタグを用いた自動分類体系構築へ向けて(クラスタリング・カテゴライズ,夏のデータベースワークショップ2007(データ工学,一般))
- ダイナミックタイムワーピング距離に基づくストリーム処理(パターン照合・パターン発見,データ工学論文)
- 電子透かし読取りのためのiアプリ高速コーナ検出アルゴリズム(画像認識, コンピュータビジョン)
- ダイナミックプログラミングに基づくストリームマッチング(セッション7b:ストリーム・スカイライン)
- SPIRAL : 隠れマルコフモデルのための高速探索手法(ポスターセッション,iDBフォーラム2008(招待講演・ポスター英語ディスカッション))
- 大量な時系列データストリームの類似検出手法(テーマセッション: 時系列・大規模メディア処理, データ工学とメディア理解との融合)
- 関係XMLデータベース用開発支援ツールの設計と実装(テーマセッション,データ工学とメディア理解との融合)
- XML木のための動的範囲ラベル付け手法
- 隠れマルコフモデルデータベースの高速ゆう度検索(データ工学研究専門委員会推薦論文,空間データベース,データ工学論文)
- TEAM Digital Commons(コンテンツ流通と著作権管理)
- 楕円体問合せのための空間変換を用いた類似探索アルゴリズム
- 楕円体問合せのための類似探索手法の提案
- カメラ付携帯電話機を用いたアナログ画像からの高速電子透かし検出方式(画像・映像処理)
- J-036 カメラ入力画像からのリアルタイム電子透かし検出方式(J.グラフィクス・画像)
- J-035 色空間範囲を考慮した電子透かし埋め込み方法の検討(J.グラフィクス・画像)
- 関係XMLデータベース用開発支援ツールの設計と実装(テーマセッション,データ工学とメディア理解との融合)
- フォルダ・プログラミング環境「POLDER」
- 高次元データのための相対的近似を用いた索引手法
- 多次元空間における類似探索手法の提案
- 階層的センサネットワークのための効率的なデータ収集手法
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- ウェアラブルセンサによるモノを用いた行動の認識について
- XML文書に対する構造を指定した全文検索方式の提案
- D-4-16 pgBoscage : PostgreSQLを用いたXMLDBの実装(D-4. データ工学,一般セッション)
- XMLデータの要約情報を用いた高速なXPath処理方法(問合せ処理,データ工学論文)
- 追記・参照型データ管理システムにおけるPush/Pull混在方式の特性評価(セッション4-C:ストリーミング技術)
- 追記・参照型データ管理システムにおけるPush/Pull混在方式の特性評価(セッション4-C:ストリーミング技術)
- エンティティ中心アプローチによるXMLDB設計手法
- 大量な時系列データストリームの類似検出手法(テーマセッション: 時系列・大規模メディア処理, データ工学とメディア理解との融合)
- TEAM Digital Commons(コンテンツ流通と著作権管理)
- 個人情報保護・活用のための契約方式(社会的課題と情報システム)
- 個人情報保護・活用のための契約方式(社会的課題と情報システム)
- ストリーム型ログデータ蓄積処理向け無停止DB分割方式の提案
- ストリーム型ログデータ蓄積処理向け無停止DB分割方式の提案
- ストリーム型ログデータ蓄積処理向け無停止DB分割方式の提案
- 電話を用いたハミング検索システム
- ハミング検索のための音楽データ自動時間正規化手法
- 低周波振動の伝播を利用した屋内での作業道具の位置検出手法
- 実世界イベント理解に向けた語彙集合の構築と評価
- センサネットワークのためのトポロジーの変化を考慮したデータ集約方式(セッション3:慶應義塾大学)
- BS-14-3 センサ情報からの実世界言語化・可視化・コンテンツ化(BS-14.ユビキタス・センサーネットワーク技術〜モノによるユビキタス環境を目指して〜,シンポジウムセッション)
- 振動波と加速度センサを用いた物体間の接触関係の取得手法(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- 振動波と加速度センサを用いた物体間の接触関係の取得手法(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- センサデータ解釈のための拡張可能な知識構築手法(第3セッション)
- 大規模センサネットワークにおける遅延の抑制を考慮したデータ収集機構の提案(UBI-3【センサネットワーク/実世界センシング】)
- 大規模センサネットワークにおける遅延の抑制を考慮したデータ収集機構の提案(UBI-3【センサネットワーク/実世界センシング】)
- 小型無線デバイスとセンサデータを用いた物体間の相対的な位置関係の推定
- タイムワーピングを考慮したトレンド検出(夏のデータベースワークショップ2007(データ工学,一般))
- タイムワーピングを考慮したトレンド検出(マイニング,夏のデータベースワークショップ2007(データ工学,一般))
- 2者間マッチングにおけるコストベースの最適化手法
- 大量データストリームの類似探索手法
- 大量データストリームの類似探索手法
- SoundCompass : ハミングによる音楽検索システム(音楽情報)
- ハミング検索用音楽データベースの分析 : 部分曲分割方法の改善に向けて
- ハミングを用いた音楽検索システム
- 時間正規化を用いたハミング検索システム
- 分散インデックスアーキテクチャによる複数データソースの同時結合方式の提案(検索と索引技術,モバイルデータベースとGIS及び一般)
- 2K-3 隠れマルコフモデルによるデータストリームのモニタリング手法(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 分散データストリーム処理における適応型リソース制御方式の検討(セッションB-2:分散処理)
- 分散データストリーム処理における適応型リソース制御方式の検討(セッションB-2:分散処理)
- 追記・参照型データ管理システムの設計と評価(ネットワークサービス,情報洪水時代のネットワークサービス)
- 分散データストリーム処理アーキテクチャの提案(夏のデータベースワークショップ2007(データ工学,一般))
- 分散データストリーム処理アーキテクチャの提案(ストリーム処理,夏のデータベースワークショップ2007(データ工学,一般))
- XMLストリーム処理 : XPath評価からSVGレンダリングまで(オフィスにおけるデジタルドキュメント/コンテンツ管理技術及び一般)
- XMLストリーム処理 : XPath評価からSVGレンダリングまで(オフィスにおけるデジタルドキュメント/コンテンツ管理技術及び一般)
- 個人情報を保護しつつ活用する方法に関する一方式(個人情報)
- 時系列データのためのストリームマイニング技術
- コンテンツ視聴により形成される動的なコミュニティにおけるユーザ行動特性の分析
- M-002 利用者の利便性を考慮した匿名権利譲渡方式の提案(M.ネットワーク・モバイルコンピューティング)
- 情報流通過程におけるユーザ種別を考慮した協調フィルタリング方式の検討(情報選択・配信)
- ランプ型閾値秘密分散法における部分情報の復元制御
- ランプ型閾値秘密分散法における部分情報の復元制御
- 大量頻度分布データのための高速探索アルゴリズム
- ダイナミックタイムワーピングのための類似探索手法
- 楕円体問合せのための類似探索手法の提案
- 仮想包囲矩形に基づく多次元データ集合に対する近傍探索
- ビットコーディングを用いたR-treeに基づく多次元空間内近傍探索の高速化
- 6E-7 分散データストリーム処理における自律Pull制御方式の改善(クラウドと分散処理,一般セッション,ネットワーク,情報処理学会創立50周年記念)
- 6E-6 メディア処理向けクラウド基盤「虹雲」(クラウドと分散処理,一般セッション,ネットワーク,情報処理学会創立50周年記念)
- D-4-5 タグツリーによる個人コンテンツ管理システム(D-4. データ工学,一般セッション)
- ディジタル・アイデンティティの法人論的考察
- ディジタル・アイデンティティの法人論的考察
- 部分シーケンスマッチングのためのストリームアルゴリズム(データ工学,Web情報システム)
- 日常物の利用情報を用いたコンテキストサーチ
- 虹雲ノート : クラウド上でのメディア処理の連携システム(テーマセッション,大規模マルチメディアデータを対象とした次世代検索およびマイニング)
- 虹雲ノート : クラウド上でのメディア処理の連携システム(テーマセッション,大規模マルチメディアデータを対象とした次世代検索およびマイニング)
- 時間制約を持つ寄り道経路探索システムの実現と評価
- 階層的センサネットワークのための特異値分解を用いたデータ圧縮手法(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- 相関性のあるデータを集約する無線センサネットワークにおけるシンクノード決定問題の近似解法
- 端末操作ログからの情報漏えい検出 (データベース Vol.4 No.4)
- データストリームにおける効率的なパターン検出
- データストリームにおける効率的なパターン検出
- 情報拡散過程のダイナミクス:非線形モデルの提案と情報予測
- 大規模Webクリックデータのためのイベント予測
- 手首に装着したカメラ付きセンサデバイスを用いた行動認識手法(モバイルコンピューティング,ユビキタス・センサネットワークを支えるシステム開発論文)
- 乾電池を模したセンサノードによる携帯型電化製品の利用の認識について(モバイルアドホックネットワーク,モバイル時代を支える次世代無線技術,フィールドセンシング及び一般)
- 振動波と加速度センサを用いた物体間の接触関係の取得手法