データベースの頻出アイテム集合を表すゼロサプレス型BDDの変数順序付けの理論的考察
スポンサーリンク
概要
- 論文の詳細を見る
ゼロサプレス型BDD(Zero-suppressed Binary Decision Diagram, ZBDD)を用いて,データベースの頻出アイテム集合を高速に抽出しコンパクトに表現する新しい手法が提案されている.一般にZBDDは変数の順序付けによりそのサイズが著しく変化することが知られているが,頻出アイテム集合を表現する場合の順序付けの影響はあまり深く研究されていなかった.本稿では,変数順序付けによりZBDDのサイズが指数関数的に変化する人工的な例題を作成できることを示し,2つの典型的な例題について,指数関数的な影響が生じる理由を理論的に考察する.
- 社団法人電子情報通信学会の論文
- 2007-02-26
著者
-
湊 真一
北海道大学大学院情報科学研究科
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
北海道大学 大学院情報科学研究科
関連論文
- BDD上の命題化計算に基づくEMアルゴリズム
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (コンピュータシステム)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (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)
- 論理合成技術
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDD(二分決定グラフ)とその応用
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム (デザインガイア'99--システム設計とCAD技術及び一般)
- ゼロサプレス型BDDを用いた系列長制限つき正規表現処理方法
- ベイジアンネットワークと離散構造処理系 (特集 ベイジアンネットワークの最先端)
- ベイジアンネットワークと離散構造処理系(ベイジアンネットワークの最先端)
- 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回)全国大会)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- F-024 ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成とその評価(F分野:人工知能・ゲーム,一般論文)
- 頻出パターンマイニングのためのゼロサプレス型BDDの変数順序付け方法とその評価(データマイニング,データ工学論文)
- F-011 頻出パタンマイニングのためのゼロサプレス型BDDの変数順序付け方法の高速化の検討(F分野:人工知能・ゲーム)
- F_019 データベース解析のためのゼロサプレス型二分決定グラフの簡単化について(F分野:人工知能・ゲーム)
- データベース解析のためのゼロサプレス型二分決定グラフの簡単化に関する考察 (テーマ:特集「ウェブデータの知的処理」および一般)
- ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成 (特集 「知識発見の生命科学への応用」および一般)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- F-013 ゼロサプレス型BDDを用いた無順序n-gram表現法の性能評価(F分野:人工知能・ゲーム)
- F-020 コルモゴロフ複雑性に基づく画像圧縮と分類に関する実験と考察(人工知能・ゲーム,一般論文)
- F-012 頻出パタン集合を表現する二分決定グラフの変数順序改善法に関する実験と考察(F分野:人工知能・ゲーム)
- D-009 ZDDを用いた頻出パタン演算によるWebテキストデータからの知識発見とその評価(D分野:データベース,一般論文)
- F-061 ベイジアンネットワークを表現するZDDの初期変数順序付け方法の改良(人工知能・ゲーム,一般論文)
- D-031 頻出パタン抽出アルゴリズム「LCM over ZDDs」の変数順序付けの影響に関する考察(データベース,一般論文)
- F-050 ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付けに関する実験と考察(人工知能・ゲーム,一般論文)
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 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湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- 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学生シンポジウム,シンポジウムセッション)
- 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の技法と離散構造処理系
- ZDDを用いた新たな列挙手法
- 順列二分決定グラフを用いたパターン回避順列の列挙索引化
- 最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ
- 写像枝を用いた系列二分決定グラフ
- 写像枝を用いた系列二分決定グラフの効率化
- ゼロサプレス型二分決定グラフによる圧縮と知識発見
- ゼロサプレス型二分決定グラフによる圧縮と知識発見
- 組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化
- 系列二分決定グラフを操作するための豊富な演算体系の構築