木分解の圧縮および解集合プログラミングによる問合せ

• Item type: SIG Technical Reports(1)
• 公開日: 2021-12-20
• タイトル: 木分解の圧縮および解集合プログラミングによる問合せ
• タイトル / 言語: en
• タイトル: Tree Decomposition Compression Using Tree Grammar and Query Processing Based on Answer Set Programming
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: テキスト処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学大学院情報学研究科
• 著者所属: 名古屋大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University
• 著者名: 小島, 和之; 関, 浩之
• 著者名(英): Kazuyuki, Kojima; Hiroyuki, Seki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフの木分解は，グラフデータへの問合せ処理に対する有効なアプローチであるが，木分解自体に大きな計算量を要することが多い．筆者らはこれまで木分解結果を圧縮し直接問合せを行う手法を提案した．しかしこの手法は個々の問題ごとに圧縮データを前提としてアルゴリズムを記述しなければならないという問題があった．そこで本研究では，問合せ処理に解集合プログラミングを利用し，圧縮データ構造を意識せずに記述したアルゴリズムを，圧縮データを操作するプログラムに変換する手法を提案した．さらに提案手法に基づく問合せ実行ツールを Clingo と C++ によって実装した．本稿では提案手法を説明した後，最大独立集合問題，3 彩色問題に対する問合せアルゴリズムを解集合プログラミングで記述した実験結果を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Tree decomposition of a graph is an effective approach to solving problems for large graphs while the decomposition itself needs much time in general. In the previous work, we proposed a method of compressing a decomposed tree and directly manipulating the compressed data. However, a query must be manually written assuming a compressed data. In this paper, we propose a query processing method based on answer set programming. A user can write a query in a declarative way without assuming a compressed data and the query can be translated into a program that directly manipulates a compressed data. The paper shows the experimental results conducted in our prototype system implemented by Clingo and C++.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 研究報告データベースシステム（DBS）; 巻 2021-DBS-174, 号 3, p. 1-6, 発行日 2021-12-20
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-871X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会