WEKO3
-
RootNode
アイテム
大規模ハイパーグラフからZDDの高速な構築アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/91764
https://ipsj.ixsq.nii.ac.jp/records/91764b3a1db61-01ee-4bd7-ae21-db2931697470
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL13144001.pdf (643.0 kB)
|
Copyright (c) 2013 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-05-10 | |||||||
| タイトル | ||||||||
| タイトル | 大規模ハイパーグラフからZDDの高速な構築アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Fast Construction of ZDDs from Large-scale Hypergraphs | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 科学技術振興機構ERATO湊離散構造処理系プロジェクト | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| ERATO MINATO Discrete Structure Manipulation System Project, Japan Science and Technology Agency | ||||||||
| 著者名 |
戸田貴久
× 戸田貴久
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | ハイパーグラフはグラフの一般化であり，幅広い種類の情報をモデル化できるので，計算機科学に多くの応用がある．ZDDはハイパーグラフを表現するための圧縮データ構造であり，ハイパーグラフを操作する実際的に効率の良いさまざまな演算が考案されている．これらのZDD演算を通して組合せ問題を計算する手法は，計算が困難な大規模問題に対して有効であることが報告されている．この手法において，ハイパーグラフをZDDに効率的に圧縮する処理は重要である．本研究では，ハイパーグラフをZDDに圧縮する高速アルゴリズムを提案し，計算量の解析を行う．さらに，様々な種類のデータセットを用いた比較実験により，既存手法よりも高速かつ省メモリに動作することを確認する． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We present an algorithm to compress hypergraphs into the data structure ZDDs and analyze the computational complexity. Since a ZDD provides an approach to solve large-scale problems that are difficult to compute in a reasonable amount of time and space, it is important to compress hypergraphs efficiently. Our algorithm uses multikey Quicksort given by Bentley and Sedgewick. By conducting experiments with various datasets, we show that our algorithm is significantly faster and requires smaller memory than an existing method. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2013-AL-144, 号 1, p. 1-6, 発行日 2013-05-10 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
