講演抄録/キーワード |
講演名 |
2014-01-29 09:20
マルチコアおよびGPUを用いたグラフ型データベースの性能評価 ○森島 信・松谷宏紀(慶大) VLD2013-121 CPSY2013-92 RECONF2013-75 |
抄録 |
(和) |
グラフ型データベースは、データをグラフ形式で蓄積し処理するデータベースである。グラフ型データベースはノード間の関係性を表現するのに向いているため、SNS(Social Networking Service) やソーシャルグラフを基にしたリコメンデーションエンジンへの応用が期待されている。
グラフ型データベースで最も計算量が多い処理は、グラフの探索である。本論文では、グラフ探索処理の並列化とGPU による高速化を実現し、その性能を評価する。
ここではグラフ型データベースNeo4j を対象に、Dijkstra 法やA*法を高速化する。評価では、Facebook の次数分布を基にした100,000 ノードのグラフに対して探索を行ったときの計算時間を測定した。データ構造を変える際のオーバーヘッドを含めない場合は、オリジナルのNeo4j と比べて、8 ノードで並列化すると、Dijkstra 法において16.2 倍、A*法において13.8 倍高速化できた。一方、GPU では、Dijkstra 法において26.2 倍、A*法において32.8 倍高速化できた。オーバーヘッドを考慮しても、この性能向上は有意である。 |
(英) |
Graph databases use graph structures to store data sets as nodes, edges, and properties. They are used to store and search the relationships between a large number of nodes, such as social networking services and recommendation engines that use customer social graphs.
Since graph search queries typically require high computation power, in this paper, we accelerate the graph search functions (Dijkstra and A* algorithms) of a graph database Neo4j using multicore and graphics proceccing units (GPUs). We use 100,000-node graphs generated based on a degree distribution of Facebook social graph for evaluations. Although our initial evaluation results do not include overhead of building extra data structures, the results show that, compared to the original Neo4j, the 8-core parallelized version improves the Dijkstra and A* search performance by 16.2x and 13.8x, respectively. The GPU based implementation improves the Dijkstra and A* search performance by 26.2x and 32.8x, respectively. |
キーワード |
(和) |
構造型ストレージ / グラフ型データベース / GPU / マルチコア / / / / |
(英) |
Structured storage / graph database / GPUs / multicore / / / / |
文献情報 |
信学技報, vol. 113, no. 417, CPSY2013-92, pp. 113-118, 2014年1月. |
資料番号 |
CPSY2013-92 |
発行日 |
2014-01-21 (VLD, CPSY, RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2013-121 CPSY2013-92 RECONF2013-75 |
研究会情報 |
研究会 |
IPSJ-SLDM CPSY RECONF VLD |
開催期間 |
2014-01-28 - 2014-01-29 |
開催地(和) |
慶応義塾大学 日吉キャンパス |
開催地(英) |
Hiyoshi Campus, Keio University |
テーマ(和) |
FPGA応用および一般 |
テーマ(英) |
FPGA Applications, etc |
講演論文情報の詳細 |
申込み研究会 |
CPSY |
会議コード |
2014-01-SLDM-CPSY-RECONF-VLD |
本文の言語 |
日本語 |
タイトル(和) |
マルチコアおよびGPUを用いたグラフ型データベースの性能評価 |
サブタイトル(和) |
|
タイトル(英) |
Performance Evaluation of Graph Database using Multicore and GPU |
サブタイトル(英) |
|
キーワード(1)(和/英) |
構造型ストレージ / Structured storage |
キーワード(2)(和/英) |
グラフ型データベース / graph database |
キーワード(3)(和/英) |
GPU / GPUs |
キーワード(4)(和/英) |
マルチコア / multicore |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
森島 信 / Shin Morishima / モリシマ シン |
第1著者 所属(和/英) |
慶應義塾大学 (略称: 慶大)
Keio University (略称: Keio Univ.) |
第2著者 氏名(和/英/ヨミ) |
松谷 宏紀 / Hiroki Matsutani / マツタニ ヒロキ |
第2著者 所属(和/英) |
慶應義塾大学 (略称: 慶大)
Keio University (略称: Keio Univ.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2014-01-29 09:20:00 |
発表時間 |
25分 |
申込先研究会 |
CPSY |
資料番号 |
VLD2013-121, CPSY2013-92, RECONF2013-75 |
巻番号(vol) |
vol.113 |
号番号(no) |
no.416(VLD), no.417(CPSY), no.418(RECONF) |
ページ範囲 |
pp.113-118 |
ページ数 |
6 |
発行日 |
2014-01-21 (VLD, CPSY, RECONF) |
|