本資料は、掲載誌(URI)等のリンク先にある学位授与機関のWebサイトやCiNii Dissertationsから、本文を自由に閲覧できる場合があります。
博士論文
国立国会図書館館内限定公開
収録元データベースで確認する
国立国会図書館デジタルコレクション
デジタルデータあり
公開元のウェブサイトで確認する
DOI[10.14943/doctoral.k14282]のデータに遷移します
Studies on New Tractable Indexing Structures and Rapid Compilation Methods for Graph-Substructures
- 国立国会図書館永続的識別子
- info:ndljp/pid/11570298
国立国会図書館での利用に関する注記
資料に関する注記
一般注記:
- Knowledge compilation has been intensely studied in the field of artificial intelligence.Knowledge compilation is, roughly describing, take some data ...
書店で探す
障害者向け資料で読む
全国の図書館の所蔵
国立国会図書館以外の全国の図書館の所蔵状況を表示します。
所蔵のある図書館から取寄せることが可能かなど、資料の利用方法は、ご自身が利用されるお近くの図書館へご相談ください
書店で探す
障害者向け資料で読む
書誌情報
この資料の詳細や典拠(同じ主題の資料を指すキーワード、著者名)等を確認できます。
デジタル
- 資料種別
- 博士論文
- タイトル
- 著者・編者
- 菅谷, 輝治
- 著者標目
- 出版年月日等
- 2020-09-25
- 出版年(W3CDTF)
- 2020-09-25
- 並列タイトル等
- グラフ部分構造を扱う新規索引構造と高速コンパイル法に関する研究
- 寄与者
- 吉岡, 真治有村, 博紀堀山, 貴史
- 授与機関名
- 北海道大学
- 授与年月日
- 2020-09-25
- 授与年月日(W3CDTF)
- 2020-09-25
- 報告番号
- 甲第14282号
- 学位
- 博士(情報科学)
- 博論授与番号
- 甲第14282号
- 本文の言語コード
- eng
- NDC
- 対象利用者
- 一般
- 一般注記
- Knowledge compilation has been intensely studied in the field of artificial intelligence.Knowledge compilation is, roughly describing, take some data with “certain” property,then change it into a data structure, which supports varieties of queries or transformation. Here, the data structure is called tractable indexing structure and the process to change the data into tractable indexing structure is called compilation. Among the tractable indexing structures, BDD is the most fundamental and has been studied for a long time.Recently, there have been two directions in the subsequent studies based on BDDs.The first direction is to enable succinctness. Darwiche et al. presented a knowledge compilation map. In knowledge compilation map, some superset structures of BDD are proposed. While the index size of BDDs are bounded with path-width of the input CNF, these superset structures in knowledge compilation map is bound with tree-width of the input CNF.The second direction is the application to graph-substructure. ZDD is a tractable indexing structure that changed the default value of BDD from “do not care” to “does not exist”. This property of ZDD called zero-suppression makes ZDD to be appropriate to represent a set of family, especially graph-substructures. As an efficient compilation method of ZDD, frontier-based search is known.An important issue of today is how to redesign ZDD and frontier-based search to achieve more efficient compilation of graph-substructures. ZSDD is a remarkable preceding work to cope with this task. ZSDD is an extension of ZDD and more succinct than ZDD in general. As a result, ZSDD’s compilation method runs faster than that of ZDD’s. However, since ZSDD is strongly structured, its compilation method become more complicated than ordinal frontier-based search. As a result, the overhead of computation is inevitable. The key issue to make the compilation much faster is how to reduce the overhead of computation.In this thesis, we introduce a new tractable indexing structure and a compilation method for graph-substructures. Our tractable indexing structure is called structured Z-d-DNNF and its compilation method is called merging frontier-based search. Since our structure is less structured than ZSDD, the capability of our structure to support query or transformation is lower than that of ZSDD. However, as trade-off, its simple structure makes the compilation method more efficient. With the theoretical analysis and the experimental result, we show that our compilation method runs faster than the previous method in many cases.In Chapter 3, we introduce our structure, structured Z-d-DNNF. We introduced zero-suppression to structured Z-d-DNNF same as ZDDs or ZSDDs. In addition, we present a new system of tractable indexing structure called zero-suppressed knowledge compilation map. It is a system of structures that has adopted zero-suppression to the whole structures of knowledge compilation map. Zero-suppressed knowledge compilation map has ZDD as basis instead of BDD. In Chapter 4 and Chapter 5, we prose our compilation method, merging frontier-based search. Merging frontier-based search is an extension of conventional frontier-based search. Unlike ordinal ZDD, we must “merge” the states of searching branches to compile structured Z-d-DNNF. We apply our compilation method to the independent set in Chapter 4 and s-t paths in Chapter 5. Finally, in Chapter 6, we conclude this thesis and discuss the future work.(主査) 教授 吉岡 真治, 教授 有村 博紀, 教授 堀山 貴史情報科学研究科(情報理工学専攻)
- DOI
- 10.14943/doctoral.k14282
- 国立国会図書館永続的識別子
- info:ndljp/pid/11570298
- コレクション(共通)
- コレクション(障害者向け資料:レベル1)
- コレクション(個別)
- 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
- 収集根拠
- 博士論文(自動収集)
- 受理日(W3CDTF)
- 2020-11-10T19:58:22+09:00
- 作成日(W3CDTF)
- 2020-07
- 記録形式(IMT)
- PDF
- オンライン閲覧公開範囲
- 国立国会図書館内限定公開
- デジタル化資料送信
- 図書館・個人送信対象外
- 遠隔複写可否(NDL)
- 可
- 連携機関・データベース
- 国立国会図書館 : 国立国会図書館デジタルコレクション