逆順の系列集合を表すSeqBDDの構築
スポンサーリンク
概要
- 論文の詳細を見る
トライなどの接頭辞の共通部分を同じグラフで表現する系列集合を表すデータ構造において,系列集合に含まれる全ての系列を逆順にした系列集合を効率良く構築できると,接尾辞を指定した系列の検索を効率良く行うことができる.これは,逆順の系列集合に対しての接頭辞を指定した系列の検索が,元の系列集合に対しての接尾辞による検索に対応するからである.本稿では,接頭辞と接尾辞の共通部分を同じグラフで表現するデータ構造の系列二分決定グラフ(Sequence Binary Decision Diagram, SeqBDD)で系列集合が与えられたときに,与えられた系列集合の逆順の系列集合を表すSeqBDDを構築する手法を示す.提案するアルゴリズムは,SeqBDDの節点をトポロジカルソートに基づいた順番に処理していくことで,同じ節点についての処理を一度だけ行う.このため,同じ節点についての処理を何度も行う単純な再帰的手法よりも効率が良い.実験により,系列間での接頭辞や接尾辞の共有量が多く,SeqBDDで効率良く表現できるデータの場合,本手法が単純な手法と比べて効率良く動作することを確認した.
- 2011-04-15
著者
-
山下 茂
立命館大学情報理工学部
-
湊 真一
北海道大学大学院情報科学研究科
-
湊 真一
函館五稜郭病院
-
湊 真一
Ntt光ネットワークシステム研究所
-
湊 真一
Ntt 未来ねっと研
-
山下 茂
立命館大学
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理系プロジェクト
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
Minato Shin-ichi
Graduate School Of Information Science And Technology Hokkaido University
-
青木 洋士
立命館大学情報理工学部
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構
-
湊 真一
Ntt光ネットワーク研究所
-
湊 真一
北海道大学 大学院情報科学研究科
-
青木 洋士
立命館大学理工学研究科
-
湊 真一
京都大学大学院情報学研究科:科学技術振興機構ERATO湊離散構造処理プロジェクト
関連論文
- 量子計算の並列シミュレーションにおける通信量削減手法(計算論,計算モデル)
- BDD上の命題化計算に基づくEMアルゴリズム
- 量子探索アルゴリズムとその利用
- FPGAのスイッチマトリクスを対象としたソフトエラー対策(チップ間通信,ルーティング,インターコネクト,デザインガイア2008-VLSI設計の新しい大地)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (コンピュータシステム)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (VLSI設計技術)
- Flexcastによる段階的導入に優れたマルチキャストシステムの設計と実装(ネットワーク・並列分散システムソフトウェア, システム開発論文)
- Flexcastに基づくマルチキャストシステムの開発とその方式設計について(映像通信,コンテンツ配信ネットワーク,マルチキャスト,一般)
- Flexcastによるインターマルチキャスティング方式の提案と日米映像配信実験(映像通信, コンテンツ配信ネットワーク, マルチキャスト, 一般)
- JGNを介した大規模映像配信プラットフォーム(新しいトラヒックモデルと性能評価及び一般)
- B-7-66 リアルタイムストリーム配信における FEC 適用時の課題に関する一考察
- B-7-47 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (3) 日米間超長距離ネットワークにおける実証実験
- B-7-46 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (2) 動的アドレスマッピングによるオンデマンド IP マルチキャストトンネリング
- B-7-45 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (1) Flexcast と IP マルチキャストの連携方式
- BS-5-5 漏洩者の特定と配信停止が可能なマルチキャスト配信方式(BS-5. ネットワークサービスのセキュリティ技術の展開,シンポジウムセッション)
- B-7-4 ネットワークによるフロー切り替えを行うマルチキャスト電子透かし方式の検討(B-7.情報ネットワーク,一般講演)
- B-7-31 トラヒックの平滑化とFECによる講義ノート映像品質の改善(B-7.情報ネットワーク, 通信2)
- Flexcastを用いた講義ノート多地点同報配信システムの検討(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- FlexcastとJavaAppletに基づくプログラマブルな多地点同報配信アプリケーションの実装法(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- B-7-73 MulticastVNCを用いた講義ノート配信システムのトラヒック特性評価(B-7. 情報ネットワーク, 通信2)
- ベイジアンネットワークと離散構造処理系 (特集 ベイジアンネットワークの最先端)
- ベイジアンネットワークと離散構造処理系(ベイジアンネットワークの最先端)
- 5.メディア系異分野共同研究プロジェクト(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- D-1-7 並列ビット分配にもとづいた効率的な正規表現照合アルゴリズム(D-1.コンピュテーション,一般セッション)
- BDD/ZDDを用いたペントミノパズルの解の列挙
- 非巡回正規表現に対する効率的なパターン照合
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- 命題論理に基づく確率モデルのための二部決定グラフと順序符号化を用いた効率的なEMアルゴリズム(一般講演(構造学習・ベイジアンネット・確率推論),機械学習とその応用)
- Increasing yield using partially-programmable circuits (VLSI設計技術)
- Increasing yield using partially-programmable circuits (ディペンダブルコンピューティング)
- 6ZK-10 二分決定グラフを用いた数独パズルの解探索と列挙(情報爆発時代におけるストリームデータと実世界情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 3ZP-5 ZDDを用いた立体ペントミノパズルの解の列挙(情報爆発時代におけるデータマイニング・アルゴリズム,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 高信頼セルによる演算器の耐故障性と遅延時間の評価(ARC-11:高信頼性および応用システム,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 少品種高信頼セルによる演算器の提案と評価(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- 少品種高信頼セルによる演算器の提案と評価(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- 少品種高信頼セルによる演算器の提案と評価(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- 少品種高信頼セルによる演算器の提案と評価(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- 細粒度命令分解と少品種セルによる高信頼化アーキテクチャの提案(Inventive and Creative Architecture特別セッションII)
- 少品種高信頼セルを用いた高信頼回路設計手法と信頼性評価手法の提案
- 少品種高信頼セルを用いた高信頼回路設計手法と信頼性評価手法の提案
- 少品種高信頼セルを用いた高信頼回路設計手法と信頼性評価手法の提案
- 少品種高信頼セルを用いた高信頼回路設計手法と信頼性評価手法の提案
- 少品種高信頼セルを用いた高信頼回路設計手法と信頼性評価手法の提案
- 少品種高信頼セルを用いた高信頼回路設計手法と信頼性評価手法の提案
- 少品種高信頼セルを用いた高信頼回路設計手法と信頼性評価手法の提案
- 高信頼セルによる回路の信頼性評価(ディペンダブル設計,デザインガイア2008-VLSI設計の新しい大地)
- 高信頼セルによる回路の信頼性評価(ディペンダブル設計,デザインガイア2008-VLSI設計の新しい大地)
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- SRAMベースFPGAにおける耐ソフトエラーLUT構成法(リコンフィギャラブルシステム2,デザインガイア2007-VLSI設計の新しい大地を考える研究会)
- F-024 ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成とその評価(F分野:人工知能・ゲーム,一般論文)
- 頻出パターンマイニングのためのゼロサプレス型BDDの変数順序付け方法とその評価(データマイニング,データ工学論文)
- F-011 頻出パタンマイニングのためのゼロサプレス型BDDの変数順序付け方法の高速化の検討(F分野:人工知能・ゲーム)
- F_019 データベース解析のためのゼロサプレス型二分決定グラフの簡単化について(F分野:人工知能・ゲーム)
- データベース解析のためのゼロサプレス型二分決定グラフの簡単化に関する考察 (テーマ:特集「ウェブデータの知的処理」および一般)
- ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成 (特集 「知識発見の生命科学への応用」および一般)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- F-013 ゼロサプレス型BDDを用いた無順序n-gram表現法の性能評価(F分野:人工知能・ゲーム)
- VLIW型命令キューを持つOROCHIの命令スケジューリング機構(プロセッサアーキテクチャ(1),「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- F-020 コルモゴロフ複雑性に基づく画像圧縮と分類に関する実験と考察(人工知能・ゲーム,一般論文)
- F-012 頻出パタン集合を表現する二分決定グラフの変数順序改善法に関する実験と考察(F分野:人工知能・ゲーム)
- D-009 ZDDを用いた頻出パタン演算によるWebテキストデータからの知識発見とその評価(D分野:データベース,一般論文)
- F-061 ベイジアンネットワークを表現するZDDの初期変数順序付け方法の改良(人工知能・ゲーム,一般論文)
- D-031 頻出パタン抽出アルゴリズム「LCM over ZDDs」の変数順序付けの影響に関する考察(データベース,一般論文)
- F-050 ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付けに関する実験と考察(人工知能・ゲーム,一般論文)
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 1.量子コンピュータ入門(講義・研究発表の概要,信州冬の学校2009,地域スクール報告)
- 高信頼セルによる回路の信頼性評価(ディペンダブル設計,デザインガイア2008-VLSI設計の新しい大地-)
- 量子計算の並列シミュレーションにおける通信量削減手法(HPC-8:アプリケーション,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- DS-1-4 耐故障性量子計算におけるエラー訂正回数の削減手法(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- ZDDを用いたパスの列挙とその性能評価
- D-4-3 共起成分の含意関係に基づく文献データベースからの共著関係の抽出(D-4. データ工学,一般セッション)
- πDD:順列集合を演算処理する二分決定グラフ
- 劣モジュラ性を用いた特徴集合列挙(離散系と機械学習,テキスト・Webマイニング,一般)
- 逆順の系列集合を表すSeqBDDの構築
- 二分決定グラフ(BDD)を活用したデータマイニング・知識発見技術の最近の話題(「自動化:推論,発見,学習,データマイニング」及び一般)
- データベースの頻出アイテム集合を表すゼロサプレス型BDDの変数順序付けの理論的考察
- VSOP: ゼロサプレス型BDDに基づく「重み付き積和集合」計算プログラム
- AI-1-5 大規模な離散構造データを扱うためのGPU利用法の検討(AI-1.GPUを用いた高速化技術とそのVLSI設計への応用,依頼シンポジウム,ソサイエティ企画)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- ERATO湊離散構造処理系プロジェクトの概要とシステム設計分野の研究について(FPGA応用)
- 東日本大震災での短縮URLによるサーバ負荷分散とアクセス分析(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- 高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- ERATO湊離散構造処理系プロジェクトの概要と最近の研究状況について(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- 写像枝を用いた系列二分決定グラフ (Theoretical Foundations of Computing)
- 組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化 (Theoretical Foundations of Computing)
- 系列二分決定グラフを操作するための豊富な演算体系の構築 (Theoretical Foundations of Computing)
- ベイジアンネットワークとZDDに関する最近の研究状況について (特集 「ベイジアンネットワークとその応用」および一般)
- 招待講演 フロンティア法 : BDD/ZDDを用いた高速なグラフ列挙索引化の技法 (情報ネットワーク)
- 最先端の開拓者たち 湊真一氏 北海道大学大学院 情報科学研究科 教授 世界的権威が認めた超高速アルゴリズム 電力危機に挑む
- 5.ZDDを用いた新たな列挙手法(広がる列挙の技術-列挙による問題解決アプローチ-)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)