お知らせ 研究会の開催と会場に参加される皆様へのお願い(2022年6月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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 
ページ数
発行日 2014-01-21 (VLD, CPSY, RECONF) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会