| Presentation | 2021-05-13 Graph Reordering while Acquiring Graph Data Managed Distributedly by Random Walk Kohei Tsuchida, Kunitake Kaneko, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | It is known that cache misses occur so many times, which leads to slow down the calculation speed while graph processing without graph reordering. In order to reduce cache misses, various reordering methods have been proposed. However, in the situation of acquiring graph data managed distributedly by random walk, applying exiting reordering methods takes a high cost due to waiting for finish of random walk. In this paper, Sequential and DBG Early Estimation (DBG-EE) are proposed as methods while acquiring graph data. Sequential especially consider continuity of node ID by reordering in the order of visiting nodes. DBG-EE consider access locality by reordering based on DBG, which is one of the best exiting methods. Our evaluation comparing to DBG with a real world graph data shows that the memory usage for reordering decreased by 41.9 % in Sequential, and 35.4 % in DBG-EE at most. Additionally, the total time from acquiring graph data to PageRank calculation decreased by 4.5 % in Sequential, and 10.3 % in DBG-EE at most. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Distributed graph management / graph processing / graph reordering / cache miss / random walk / DBG |
| Paper # | NS2021-20 |
| Date of Issue | 2021-05-06 (NS) |
| Conference Information | |
| Committee | NS |
|---|---|
| Conference Date | 2021/5/13(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | High level protocol, Networking technologies (IP and high-layer routing/filtering, Multicast, Quality/Routing control), IP network application technologies (P2P, P4P, Overlay, SIP, NGN), Network system related technologies (System configuration, Interface, Architecture, Hardware/Software/Middleware), Security, Blockchain etc. |
| Chair | Akihiro Nakao(Univ. of Tokyo) |
| Vice Chair | Tetsuya Oishi(NTT) |
| Secretary | Tetsuya Oishi(NTT) |
| Assistant | Shinya Kawano(NTT) |
| Paper Information | |
| Registration To | Technical Committee on Network Systems |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Graph Reordering while Acquiring Graph Data Managed Distributedly by Random Walk |
| Sub Title (in English) | |
| Keyword(1) | Distributed graph management |
| Keyword(2) | graph processing |
| Keyword(3) | graph reordering |
| Keyword(4) | cache miss |
| Keyword(5) | random walk |
| Keyword(6) | DBG |
| 1st Author's Name | Kohei Tsuchida |
| 1st Author's Affiliation | Keio University(Keio Univ.) |
| 2nd Author's Name | Kunitake Kaneko |
| 2nd Author's Affiliation | Keio University(Keio Univ.) |
| Date | 2021-05-13 |
| Paper # | NS2021-20 |
| Volume (vol) | vol.121 |
| Number (no) | NS-17 |
| Page | pp.pp.32-37(NS), |
| #Pages | 6 |
| Date of Issue | 2021-05-06 (NS) |