再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法(システム設計技術(1),デザインガイア2012-VLSI設計の新しい大地-)
スポンサーリンク
概要
- 論文の詳細を見る
近年、グラフ上の2点間の全てのパスを表現したZero-suppressed Binary Decision Diagram(ZDD)を高速に構築するアルゴリズムがKnuthによって発表され、ZDDを用いた新たな列挙手法が注目を集めている。この手法に基づいたこれまでのアプリケーションの多くでは、構築されたZDDに対して様々な条件によるフィルタリングを行って最終的に必要な結果を取り出している。この計算中に発生しやすいメモリ爆発を避けるため、我々は、中間的なZDD構造を構築することなく最終的なZDD構造を直接構築する手法を提案する。
- 2012-11-19
著者
-
湊 真一
NTT未来ねっと研究所
-
湊 真一
Ntt光ネットワークシステム研究所
-
湊 真一
Ntt 未来ねっと研
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理系プロジェクト
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
Ntt Lsi 研究所
-
川原 純
科学技術振興機構ERATO湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理プロジェクト
-
川原 純
独立行政法人科学技術振興機構erato湊離散構造処理系プロジェクト
-
岩下 洋哲
科学技術振興機構erato湊離散構造処理系プロジェクト:北海道大学大学院情報科学研究科
-
湊 真一
北海道大学 大学院情報科学研究科
-
湊 真一
科学技術振興機構ERATO:早稲田大学:北海道大学
-
湊 真一
京都大学大学院情報学研究科:科学技術振興機構ERATO湊離散構造処理プロジェクト
-
岩下 洋哲
独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト:北海道大学大学院情報科学研究科
-
湊 真一
北海道大学大学院情報科学研究科:独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト
-
湊 真一
北海道大学 大学院 情報科学研究科
関連論文
- 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などのオーバレイネットワーキング技術及び一般)
- 論理合成技術
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDD(二分決定グラフ)とその応用
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム (デザインガイア'99--システム設計とCAD技術及び一般)
- ゼロサプレス型BDDを用いた系列長制限つき正規表現処理方法
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム (デザインガイア'99--システム設計とCAD技術及び一般)
- ベイジアンネットワークと離散構造処理系(ベイジアンネットワークの最先端)
- 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アルゴリズム(一般講演(構造学習・ベイジアンネット・確率推論),機械学習とその応用)
- 6ZK-10 二分決定グラフを用いた数独パズルの解探索と列挙(情報爆発時代におけるストリームデータと実世界情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 3ZP-5 ZDDを用いた立体ペントミノパズルの解の列挙(情報爆発時代におけるデータマイニング・アルゴリズム,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- B-7-108 Virtual BUSにおける資源管理探索機構
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- F-024 ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成とその評価(F分野:人工知能・ゲーム,一般論文)
- ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成 (特集 「知識発見の生命科学への応用」および一般)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- F-020 コルモゴロフ複雑性に基づく画像圧縮と分類に関する実験と考察(人工知能・ゲーム,一般論文)
- D-009 ZDDを用いた頻出パタン演算によるWebテキストデータからの知識発見とその評価(D分野:データベース,一般論文)
- F-061 ベイジアンネットワークを表現するZDDの初期変数順序付け方法の改良(人工知能・ゲーム,一般論文)
- D-031 頻出パタン抽出アルゴリズム「LCM over ZDDs」の変数順序付けの影響に関する考察(データベース,一般論文)
- F-050 ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付けに関する実験と考察(人工知能・ゲーム,一般論文)
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- ZDDによるベイジアンネットワーク推論の高速化 (特集 「ベイジアン・ネットワークと応用」および一般)
- ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付け方法に関する考察 (特集 「ベイジアン・ネットワークと応用」および一般)
- ZDDを用いたパスの列挙とその性能評価
- D-4-3 共起成分の含意関係に基づく文献データベースからの共著関係の抽出(D-4. データ工学,一般セッション)
- πDD:順列集合を演算処理する二分決定グラフ
- 劣モジュラ性を用いた特徴集合列挙(離散系と機械学習,テキスト・Webマイニング,一般)
- DDMF : An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction
- 逆順の系列集合を表すSeqBDDの構築
- 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湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- BDD/ZDDの技法と離散構造処理系(離散構造処理系-知能情報処理を支えるアルゴリズムの技法)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-1 フロンティア法 : ZDDを用いた極めて高速なグラフ列挙索引化アルゴリズム(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-1 フロンティア法 : ZDDを用いた極めて高速なグラフ列挙索引化アルゴリズム(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DS-1-13 πDDのConjugacy Class計算への適用とその性能評価(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- スタンフォード大学De Micheli研究室に留学して(海外,ラボラトリーズ)
- Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
- DS-1-14 πDDの順列集合演算を用いたパンケーキ整列問題の解析法(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- グラフ列挙索引化技法の種々の問題への適用 (特集 BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- BDD/ZDDを用いたグラフ列挙索引化技法 (特集 BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- BDD/ZDDの技法と離散構造処理系
- フロンティア法による電力網構成制御(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- 種々のリンクパズルへの応用(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- グラフ列挙索引化技法の種々の問題への適用(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- BDD/ZDDを用いたグラフ列挙索引化技法(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- 特集にあたって(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- 順列二分決定グラフを用いたパターン回避順列の列挙索引化
- 最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ
- 写像枝を用いた系列二分決定グラフの効率化
- 組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化
- 系列二分決定グラフを操作するための豊富な演算体系の構築
- フロンティア法を用いた電力網解析手法(新世代・次世代ネットワーク,ネットワークとシステムの仮想化,仮想化環境の管理・監視,オーバーレイ,IPv6ネットワーク,フォトニックネットワーク及び一般)
- フロンティア法 : BDD/ZDDを用いた高速なグラフ列挙索引化の技法(新世代・次世代ネットワーク,ネットワークとシステムの仮想化,仮想化環境の管理・監視,オーバーレイ,IPv6ネットワーク,フォトニックネットワーク及び一般)
- 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法(システム設計技術(1),デザインガイア2012-VLSI設計の新しい大地-)
- 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法(システム設計技術(1),デザインガイア2012-VLSI設計の新しい大地-)
- ERATO湊離散構造処理系プロジェクトの概要と今後の展望について(ブロードバンドアクセス,ホームネットワーク,ネットワークサービス,通信利用アプリケーション,一般)
- ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造(一般)