| 講演名 | 2021-12-27 木分解の圧縮および解集合プログラミングによる問合せ 小島 和之(名大), 関 浩之(名大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフの木分解は，グラフデータへの問合せ処理に対する有効なアプローチであるが，木分解自体に大きな計算量を要することが多い．筆者らはこれまで木分解結果を圧縮し直接問合せを行う手法を提案した．しかしこの手法は個々の問題ごとに圧縮データを前提としてアルゴリズムを記述しなければならないという問題があった．そこで本研究では，問合せ処理に解集合プログラミングを利用し，圧縮データ構造を意識せずに記述したアルゴリズムを，圧縮データを操作するプログラムに変換する手法を提案した．さらに提案手法に基づく問合せ実行ツールをClingoとC++によって実装した．本稿では提案手法を説明した後,最大独立集合問題，3 彩色問題に対する問合せアルゴリズムを解集合プログラミングで記述した実験結果を示す． |
| 抄録(英) | 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++. |
| キーワード(和) | グラフ / 木分解 / 圧縮 / 解集合プログラミング / Clingo |
| キーワード(英) | graph / tree decomposition / compression / answer setprogramming / Clingo |
| 資料番号 | DE2021-16 |
| 発行日 | 2021-12-20 (DE) |
| 研究会情報 | |
| 研究会 | DE / IPSJ-DBS |
|---|---|
| 開催期間 | 2021/12/27(から1日開催) |
| 開催地（和） | 国立情報学研究所(NII) |
| 開催地（英） | |
| テーマ（和） | データ工学・データベースシステムとエンターテイメントおよび一般 |
| テーマ（英） | |
| 委員長氏名（和） | 吉田 尚史(駒澤大) |
| 委員長氏名（英） | Naofumi Yoshida(Komazawa Univ.) |
| 副委員長氏名（和） | 的野 晃整(産総研) / 鈴木 優(岐阜大) |
| 副委員長氏名（英） | Akiyoshi Matono(AIST) / Yu Suzuki(Gifu Univ.) |
| 幹事氏名（和） | 鷹野 孝典(神奈川工科大) / 新妻 弘崇(阪大) |
| 幹事氏名（英） | Kosuke Takano(Kanagawa Inst. of Tech.) / Hirotaka Niitsuma(Osaka Univ.) |
| 幹事補佐氏名（和） | 本多 賢(駒澤大) / 野宮 浩揮(京都工繊大) |
| 幹事補佐氏名（英） | Ken Honda(Komazawa Univ.) / Hiroki Nomiya(Kyoto Inst. of Tech) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Data Engineering / Special Interest Group on Database System |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木分解の圧縮および解集合プログラミングによる問合せ |
| サブタイトル（和） | |
| タイトル（英） | Tree decomposition compression using tree grammar and query processing based on answer set programming |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | 木分解 / tree decomposition |
| キーワード(3)（和/英） | 圧縮 / compression |
| キーワード(4)（和/英） | 解集合プログラミング / answer setprogramming |
| キーワード(5)（和/英） | Clingo / Clingo |
| 第 1 著者 氏名（和/英） | 小島 和之 / Kazuyuki Kojima |
| 第 1 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 第 2 著者 氏名（和/英） | 関 浩之 / Hiroyuki Seki |
| 第 2 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 発表年月日 | 2021-12-27 |
| 資料番号 | DE2021-16 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | DE-314 |
| ページ範囲 | pp.7-12(DE), |
| ページ数 | 6 |
| 発行日 | 2021-12-20 (DE) |