| 講演名 | 2013-04-24 枝刈り探索のパスへの拡張による到達可能性クエリ 矢野 洋祐, 秋葉 拓哉, 岩田 陽一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフの到達可能性は理論と応用の両方において基礎となる問題であるが,大規模なグラフ上で大量の到達可能性クエリに答えるのは依然難しい問題である.我々は本論文で,有向グラフ上でメモリ消費量を抑えながら到達可能性クエリに答える,枝刈り探索に基づいたインデクシング手法を提案する.提案手法では枝刈り探索を頂点からではなくパスから行いインデックスを作成する.我々は実験により,我々の提案手法が数千万辺規模の現実世界のグラフと人工グラフにおいて動作し,平均1μs以下で各クエリに答えられることを示した. |
| 抄録(英) | The graph reachability is a fundamental problem, both theoretically and practically. However, it is still a challenging task to answer many reachability queries on large-scale graphs. In this paper, we propose a new memory-efficient indexing method for answering reachability queries on directed graphs, based on pruned breadth-first searches. The idea behind our method is that we create indexes by conducting pruned breadth-first searches from paths instead of vertices. We experimentally show that our method scales to real and synthetic graphs with tens of millions of edges, and it can answer a query in under a microsecond on average. |
| キーワード(和) | グラフ / 到達可能性 / クエリ処理 |
| キーワード(英) | Graphs / reachability / query processing |
| 資料番号 | COMP2013-1 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2013/4/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 枝刈り探索のパスへの拡張による到達可能性クエリ |
| サブタイトル（和） | |
| タイトル（英） | Answering Reachability Queries by Extending Pruned BFSs to Paths |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / Graphs |
| キーワード(2)（和/英） | 到達可能性 / reachability |
| キーワード(3)（和/英） | クエリ処理 / query processing |
| 第 1 著者 氏名（和/英） | 矢野 洋祐 / Yosuke YANO |
| 第 1 著者 所属（和/英） | 東京大学情報理工学系研究科 Graduate School of Information Science and Technology, The University of Tokyo |
| 第 2 著者 氏名（和/英） | 秋葉 拓哉 / Takuya AKIBA |
| 第 2 著者 所属（和/英） | 東京大学情報理工学系研究科 Graduate School of Information Science and Technology, The University of Tokyo |
| 第 3 著者 氏名（和/英） | 岩田 陽一 / Yoichi IWATA |
| 第 3 著者 所属（和/英） | 東京大学情報理工学系研究科 Graduate School of Information Science and Technology, The University of Tokyo |
| 発表年月日 | 2013-04-24 |
| 資料番号 | COMP2013-1 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 14 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |