| Presentation | 2017-12-14 Dynamic Partition by Local Calculation in Large Scale Distributed Graph Environment Yuta Yasumura, Kunitake Kaneko, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph / distributed environment / partition / Parallel processing |
| Paper # | IN2017-55 |
| Date of Issue | 2017-12-07 (IN) |
| Conference Information | |
| Committee | IA / IN |
|---|---|
| Conference Date | 2017/12/14(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Hiroshima City Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
| Chair | Katsuyoshi Iida(Hokkaido Univ.) / Katsunori Yamaoka(Tokyo Inst. of Tech.) |
| Vice Chair | Rei Atarashi(IIJ) / Hiroyuki Osaki(Kwansei Gakuin Univ.) / Tomoki Yoshihisa(Osaka Univ.) / Takuji Kishida(NTT) |
| Secretary | Rei Atarashi(Tokyo Metropolitan Univ.) / Hiroyuki Osaki(TOYOTA-IT) / Tomoki Yoshihisa(NTT) / Takuji Kishida(NTT) |
| Assistant | Kenji Ohira(Tokushima Univ.) / Ryohei Banno(NTT) / Toshiki Watanabe(NEC) |
| Paper Information | |
| Registration To | Technical Committee on Internet Architecture / Technical Committee on Information Networks |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Dynamic Partition by Local Calculation in Large Scale Distributed Graph Environment |
| Sub Title (in English) | |
| Keyword(1) | graph |
| Keyword(2) | distributed environment |
| Keyword(3) | partition |
| Keyword(4) | Parallel processing |
| 1st Author's Name | Yuta Yasumura |
| 1st Author's Affiliation | Keio University(Keio Univ.) |
| 2nd Author's Name | Kunitake Kaneko |
| 2nd Author's Affiliation | Keio University(Keio Univ.) |
| Date | 2017-12-14 |
| Paper # | IN2017-55 |
| Volume (vol) | vol.117 |
| Number (no) | IN-353 |
| Page | pp.pp.55-60(IN), |
| #Pages | 6 |
| Date of Issue | 2017-12-07 (IN) |