| 講演名 | 2017-12-14 大規模分散グラフ環境における局所計算による動的パーティション 安村 有太(慶大), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 大規模分散グラフ環境における処理フレームワークは，入力されたグラフの全体の形状をまず把握し、適切な部分グラフに分割し各計算機に割り当て，要求されたグラフ演算処理を実行している．これまでこの処理を高速化するにあたり，PageRankなどの特定のクエリや，静的で形状が変化しないグラフに注目したグラフパーティション手法が研究されている．しかし，PageRank以外の重要度の指標となる次数中心性や媒介中心性を求めるような複数のクエリの対応や，ソーシャルグラフのように刻一刻と形状や規模が変化するグラフに対応するような既存手法は存在しない．そこで筆者らは，大規模分散グラフ環境におけるパーティションの動的変更手法を考案した．具体的には，大規模分散グラフ環境において，各計算機が自身の保持するグラフデータへのクエリアクセスを解析しグラフ上での重要度の偏りを測り，グラフデータ上の隣接データを持つ計算機間でグラフデータを交換することで，グラフ全体の形状を把握することなく，短い計算時間でのパーティションを実現した．提案手法により，既存手法と比べ約4.2倍グラフの探索時間を高速化することを確認した． |
| 抄録(英) | In the processing framework in the large scale distributed graph environment, the entire shape of the input graph is first grasped, divided into appropriate partial graphs, assigned to each computer, and the requested graph operation processing is executed. To accelerate this process so far, graph partitioning methods focusing on specific queries such as PageRank and static and non-changing shape graphs are studied. However, There is no method to respond to multiple queries such as finding order centrality and mediation centricity, which are indicators of importance other than PageRank, and to respond to graphs where shapes and scales change every moment like social graph. Therefore, the authors devised a dynamic change method of partitions in a large scale distributed graph environment. Specifically, in a large-scale distributed graph environment, each computer analyzes query access to graph data held by themselves, measures the degree of importance on the graph, and calculates the difference between the computers having adjacent data on the graph data By exchanging graph data, we realized partitions with short calculation time without grasping the shape of the entire graph. We confirmed that the proposed method speeds up the search time of about 4.2 times graphs compared to existing methods. |
| キーワード(和) | グラフ / 分散環境 / パーティション / 並列処理 |
| キーワード(英) | graph / distributed environment / partition / Parallel processing |
| 資料番号 | IN2017-55 |
| 発行日 | 2017-12-07 (IN) |
| 研究会情報 | |
| 研究会 | IA / IN |
|---|---|
| 開催期間 | 2017/12/14(から2日開催) |
| 開催地（和） | 広島市立大学 |
| 開催地（英） | Hiroshima City Univ. |
| テーマ（和） | 性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、IPv6 、マルチキャスト、ルーティング、DDoS及び一般 |
| テーマ（英） | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
| 委員長氏名（和） | 飯田 勝吉(北大) / 山岡 克式(東工大) |
| 委員長氏名（英） | Katsuyoshi Iida(Hokkaido Univ.) / Katsunori Yamaoka(Tokyo Inst. of Tech.) |
| 副委員長氏名（和） | 新 麗(IIJ) / 大崎 博之(関西学院大) / 義久 智樹(阪大) / 岸田 卓治(NTT) |
| 副委員長氏名（英） | Rei Atarashi(IIJ) / Hiroyuki Osaki(Kwansei Gakuin Univ.) / Tomoki Yoshihisa(Osaka Univ.) / Takuji Kishida(NTT) |
| 幹事氏名（和） | 作元 雄輔(首都大東京) / 屏 雄一郎(トヨタIT) / 木村 達郎(NTT) / 唐沢 裕明(NTT) / 松本 延孝(KDDI総合研究所) / 植田 一暁(KDDI総合研究所) |
| 幹事氏名（英） | Yusuke Sakumoto(Tokyo Metropolitan Univ.) / Yuichiro Hei(TOYOTA-IT) / Tatsuro Kimura(NTT) / Hiroaki Karasawa(NTT) / Nobutaka Matsumoto(KDDI Research) / Kazuaki Ueda(KDDI Research) |
| 幹事補佐氏名（和） | 大平 健司(徳島大) / 坂野 遼平(NTT) / 渡辺 俊貴(NEC) |
| 幹事補佐氏名（英） | Kenji Ohira(Tokushima Univ.) / Ryohei Banno(NTT) / Toshiki Watanabe(NEC) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Internet Architecture / Technical Committee on Information Networks |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 大規模分散グラフ環境における局所計算による動的パーティション |
| サブタイトル（和） | |
| タイトル（英） | Dynamic Partition by Local Calculation in Large Scale Distributed Graph Environment |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | 分散環境 / distributed environment |
| キーワード(3)（和/英） | パーティション / partition |
| キーワード(4)（和/英） | 並列処理 / Parallel processing |
| 第 1 著者 氏名（和/英） | 安村 有太 / Yuta Yasumura |
| 第 1 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 2 著者 氏名（和/英） | 金子 晋丈 / Kunitake Kaneko |
| 第 2 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 発表年月日 | 2017-12-14 |
| 資料番号 | IN2017-55 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | IN-353 |
| ページ範囲 | pp.55-60(IN), |
| ページ数 | 6 |
| 発行日 | 2017-12-07 (IN) |