| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-03-01 09:20 地理的に分散したグラフ解析のための経路再利用機能を有する非同期型 UDP Random Walk手法 ○滝沢 駿・山下剛志・金子晋丈（慶大）  IN2023-88 |
|
| 抄録 | （和） | Random Walk (RW) はグラフ解析技術として注目されている. 一方, 解析対象となるグラフデータは近年大規模化が進み, WAN における転送コストの制約やプライバシ規制のため, 一箇所に集中させず地理的に分散した環境下で保持されることが珍しくない. しかしながら, このような WAN 環境では RTT やパケットロス率が増加するだけでなく, グラフの全体把握が必要なグラフ分割も適用が困難となる. 結果として主に単一データセンター内に保存されたグラフデータを対象とする既存 RW 手法を WAN 環境に適用すると演算性能が大きく劣化する. そこで本研究では, 地理的分散環境下に適応する分散グラフ RW エンジンを提案する. 提案手法は RW 演算の独立性に注目し, UDP を使用した非同期処理を採用した. さらに Random Walker の経路再利用により通信量を削減する. RTT が 100ms, パケットロス率が 0.03% の環境での実験の結果, 提案手法は既存手法に比べ 1.6 (経路再利用なし) $sim$ 7.1 (経路再利用あり) 倍高速であることを明らかにした. また提案手法は既存手法と異なり RTT, パケットロス率が大きくグラフ分割精度が悪いほど有効であり, サーバ台数を 3 台から 7 台に増やした実験では既存手法の 39% の性能劣化に対し, 提案手法は 4% の性能向上を達成したことから, システム規模に対するスケーラビリティにも優れていることを明らかにした. |
| （英） | Random Walk (RW) is widely used in graph analysis. Graph data for analysis has been getting larger and larger in recent years, and it is not unusual for them to be kept in a geographically dispersed environment instead of being concentrated in a single location due to the limitation of transfer cost over WANs and privacy regulations. However, in such a WAN environment, not only do RTT and packet loss rate increase, but also graph partitioning, which requires an overall understanding of the graph, becomes difficult to apply. As a result, the existing RW method, which mainly targets graph data stored in a single datacenter, results in a significant degradation of computing performance when applied to a WAN environment. In this research, we propose a distributed graph RW engine that adapts to geographically distributed environments. The proposed method employs asynchronous processing using UDP communication, by paying attention to features of RW operations. Furthermore, the proposed method reduces the amount of communication by reusing Random Walker routes. Experimental results under the RTT of 100ms and packet loss ratio of 0.03% show that the proposed method is 1.6 (without route reuse) to 7.1 (with route reuse) times faster than the existing methods. Unlike existing methods, the proposed method is effective when the RTT, and packet loss rate are large and the accuracy of graph partitioning is poor. The proposed method is also found to have good scalability with respect to the system size because, in the experiment when the number of servers is increased from 3 to 7, the performance of the proposed method is improved by 4%, while that of the existing methods is degraded by 39%. | |
| キーワード | （和） | Random Walk / グラフ解析 / 非同期処理 / 分散処理 / UDP / 地理的分散 / / |
| （英） | Random Walk / graph analysis / asynchronous processing / distributed processing / UDP / Geo-Distributed / / | |
| 文献情報 | 信学技報, vol. 123, no. 398, IN2023-88, pp. 136-141, 2024年2月. | |
| 資料番号 | IN2023-88 | |
| 発行日 | 2024-02-22 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2023-88 |
|
| 研究会情報 | |
| 研究会 | NS IN |
| 開催期間 | 2024-02-29 - 2024-03-01 |
| 開催地（和） | 沖縄コンベンションセンター |
| 開催地（英） | Okinawa Convention Center |
| テーマ（和） | 一般 |
| テーマ（英） | General |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2024-02-NS-IN |
| 本文の言語 | 日本語 |
| タイトル（和） | 地理的に分散したグラフ解析のための経路再利用機能を有する非同期型 UDP Random Walk手法 |
| サブタイトル（和） | |
| タイトル（英） | Asynchronous UDP Random Walk method with path reuse for geo-distributed graph analysis |
| サブタイトル（英） | |
| キーワード(1)（和/英） | Random Walk / Random Walk |
| キーワード(2)（和/英） | グラフ解析 / graph analysis |
| キーワード(3)（和/英） | 非同期処理 / asynchronous processing |
| キーワード(4)（和/英） | 分散処理 / distributed processing |
| キーワード(5)（和/英） | UDP / UDP |
| キーワード(6)（和/英） | 地理的分散 / Geo-Distributed |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 滝沢 駿 / Shun Takizawa / タキザワ シュン |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第3著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-03-01 09:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2023-88 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.398 |
| ページ範囲 | pp.136-141 |
| ページ数 | 6 |
| 発行日 | 2024-02-22 (IN) |
[研究会発表申込システムのトップページに戻る]