文献

J-GLOBAL ID：201702261827927664   整理番号：17A0183206

分散グラフ処理におけるグラフ分割

Graph Partitioning for Distributed Graph Processing

著者 (3件)： 藤森俊匡 (大阪大 大学院情報科学研究科) ,  塩川浩昭 (筑波大 計算科学研究セ) ,  鬼塚真 (大阪大 大学院情報科学研究科)
資料名： 情報処理学会論文誌トランザクション データベース(Web)  (情報処理学会論文誌 データベース(Web))
巻： 9  号： 4  ページ： 46-56 (WEB ONLY)  発行年： 2016年12月22日 
JST資料番号： U0476A  ISSN： 1882-7799  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ソーシャルグラフやWebグラフのような大規模グラフデータの分析処理を高速に行うために分散グラフ処理技術の重要性が高まっている。分散グラフ処理では,入力となるグラフデータを分割し各計算機に割り当ててから分析処理を行う。ここで,最初のグラフ分割の品質によって分析処理中の通信コストおよびロードバランスは大きく左右される。そこで本稿では,分散グラフ処理における分析処理を高速化するようなグラフ分割手法を提案する。本手法は,Modularityに基づくグラフクラスタリングにクラスタの等粒度性という観点を加え,通信コストの削減と計算負荷の均衡化をバランス良く両立させる。我々は提案手法を既存の分散グラフ処理フレームワーク上に実装し,従来手法を用いた場合との性能比較を行った。その結果,従来手法であるHDRFを用いた場合と比較してPageRankの分析処理を最大3.2倍高速化できることを確認した。(著者抄録)

シソーラス用語： *分割 ,  ホームページ ,  *グラフ ,  *知識獲得 ,  *分散処理 ,  クラスタ化 ,  粒度【計算機】 ,  負荷分散 ,  モジュール構造 ,  頂点 ,  複製 ,  評価試験 ,  原価低減 ,  高速化
準シソーラス用語： PageRank ,  グラフ分割 ,  グラフマイニング ,  負荷均衡 ,  通信コスト

分類 (1件)： 計算理論  (JB02000A)

引用文献 (16件)：

• Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N. and Czajkowski, G.: Pregel: A system for large-scale graph processing, Proc. SIGMOD (2010).
• Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A. and Hellerstein, J.M.: Distributed GraphLab: A framework for machine learning and data mining in the cloud, PVLDB (2012).
• Gonzalez, J.E., Low, Y., Gu, H., Bickson, D. and Guestrin, C.: PowerGraph: Distributed graph-parallel computation on natural graphs, Proc. OSDI (2012).
• Xin, R.S., Gonzalez, J.E., Franklin, M.J. and Stoica, I.: GraphX: A resilient distributed graph system on Spark, Proc. GRADES (2013).
• Suri, S. and Vassilvitskii, S.: Counting triangles and the curse of the last reducer, Proc. WWW (2011).

タイトルに関連する用語 (2件)： グラフ ,  グラフ分割