講演抄録/キーワード |
講演名 |
2013-04-24 10:00
枝刈り探索のパスへの拡張による到達可能性クエリ ○矢野洋祐・秋葉拓哉・岩田陽一(東大) COMP2013-1 |
抄録 |
(和) |
グラフの到達可能性は理論と応用の両方において基礎となる問題であるが,大規模なグラフ上で大量の到達可能性クエリに答えるのは依然難しい問題である.我々は本論文で,有向グラフ上でメモリ消費量を抑えながら到達可能性クエリに答える,枝刈り探索に基づいたインデクシング手法を提案する.提案手法では枝刈り探索を頂点からではなくパスから行いインデックスを作成する.我々は実験により,我々の提案手法が数千万辺規模の現実世界のグラフと人工グラフにおいて動作し,平均$1mu{rm 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. |
キーワード |
(和) |
グラフ / 到達可能性 / クエリ処理 / / / / / |
(英) |
graph / reachability / query processing / / / / / |
文献情報 |
信学技報, vol. 113, no. 14, COMP2013-1, pp. 1-8, 2013年4月. |
資料番号 |
COMP2013-1 |
発行日 |
2013-04-17 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-1 |