電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2017-12-14 16:45
大規模分散グラフ環境における局所計算による動的パーティション
安村有太金子晋丈慶大
抄録 (和) 大規模分散グラフ環境における処理フレームワークは,入力されたグラフの全体の形状をまず把握し、適切な部分グラフに分割し各計算機に割り当て,要求されたグラフ演算処理を実行している.これまでこの処理を高速化するにあたり,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 / / / /  
文献情報 信学技報, vol. 117, no. 353, IN2017-55, pp. 55-60, 2017年12月.
資料番号 IN2017-55 
発行日 2017-12-07 (IN) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 IA IN  
開催期間 2017-12-14 - 2017-12-15 
開催地(和) 広島市立大学 
開催地(英) 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. 
講演論文情報の詳細
申込み研究会 IN 
会議コード 2017-12-IA-IN 
本文の言語 日本語 
タイトル(和) 大規模分散グラフ環境における局所計算による動的パーティション 
サブタイトル(和)  
タイトル(英) Dynamic Partition by Local Calculation in Large Scale Distributed Graph Environment 
サブタイトル(英)  
キーワード(1)(和/英) グラフ / graph  
キーワード(2)(和/英) 分散環境 / distributed environment  
キーワード(3)(和/英) パーティション / partition  
キーワード(4)(和/英) 並列処理 / Parallel processing  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 安村 有太 / Yuta Yasumura / ヤスムラ ユウタ
第1著者 所属(和/英) 慶應義塾大学 (略称: 慶大)
Keio University (略称: Keio Univ.)
第2著者 氏名(和/英/ヨミ) 金子 晋丈 / Kunitake Kaneko /
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2017-12-14 16:45:00 
発表時間 25 
申込先研究会 IN 
資料番号 IEICE-IN2017-55 
巻番号(vol) IEICE-117 
号番号(no) no.353 
ページ範囲 pp.55-60 
ページ数 IEICE-6 
発行日 IEICE-IN-2017-12-07 


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

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


IEICE / 電子情報通信学会