| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-01-23 11:10 分散型動的グラフにおけるランダムウォーク演算の負荷分散のためのグラフメンテナンス ○秋元大河・山下剛志・金子晋丈（慶大）  NS2024-172 |
|
| 抄録 | （和） | 近年，大規模グラフはパーティションに分割され複数のサーバで分散管理されている．このような環境では，各サーバの通信やメモリの負荷低減や分散が必要であり，特にグラフ変化に合わせて負荷低減のためにパーティション間で頂点を移動するグラフメンテナンスが注目されている．しかし，既存手法はグラフ解析において重要なランダムウォーク(RW)演算においてサーバ間通信負荷を分散することができない．これは，主たる通信負荷となる，ランダムウォーカーがパーティション境界（サーバ間）を跨ぐ回数(パーティションの跨がれ回数)が，単純にパーティション間エッジ数やパーティションサイズだけで決定されないためである．そこで本研究では，跨がれ回数に注目してRWで生じる通信負荷を分散するメンテナンス手法を提案する．具体的には，計測した各パーティション境界の跨がれ回数に基づいて，マスタサーバがパーティション間で移動すべき頂点を決定し，跨がれ回数が減少するように移動させる．このとき，跨がれ回数が大きいパーティションの境界頂点を優先的に移動させることで，跨がれ回数のばらつきを抑え通信負荷を低減し負荷を分散させる．評価の結果，提案手法は既存手法と比べて，RWで発生するサーバ間通信の通信量の標準偏差を，最大で82%軽減できることが明らかになった． |
| （英） | Recently, large-scale graphs have been partitioned and distributed across multiple servers. In such an environment, it is necessary to reduce and distribute the communication and memory load on each server. In particular, graph maintenance that moves vertices between partitions to reduce the load as the graph changes has attracted attention. However, existing methods cannot distribute the communication load between servers for Random Walk (RW) operations, which are important in graph analysis. This is because the number of times a random walker straddles a partition boundary (between servers), which is the main communication load, is not simply determined by the number of inter-partition edges or partition size. Therefore, we propose a maintenance method to distribute the communication load caused by RW by focusing on the number of crossing times. Specifically, the master server determines the vertices that should be moved between partitions based on the measured number of crossing times at each partition boundary, and moves them so that the number of crossing times decreases. In this process, the vertices of partitions with a large number of crossings are moved preferentially to reduce the variation in the number of crossings, thereby reducing the communication load and distributing the load. The evaluation results show that the proposed method can reduce the standard deviation of inter-server communication volume generated by RW by up to 82% compared to the existing method. | |
| キーワード | （和） | 動的グラフ / 負荷分散 / ランダムウォーク / メンテナンス / / / / |
| （英） | Dynamic Graphs / Load Balancing / Random Walk / Maintenance / / / / | |
| 文献情報 | 信学技報, vol. 124, no. 344, NS2024-172, pp. 13-18, 2025年1月. | |
| 資料番号 | NS2024-172 | |
| 発行日 | 2025-01-16 (NS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2024-172 |
|
| 研究会情報 | |
| 研究会 | NS NWS |
| 開催期間 | 2025-01-23 - 2025-01-24 |
| 開催地（和） | 東淀川区民会館 + オンライン開催 |
| 開催地（英） | Higashi-Yodogawa Community Center + Online |
| テーマ（和） | NWソフトウエア(ソフトウエアアーキテクチャ，ミドルウエア)，NWアプリケーション，SOA/SDP，NGN/IMS/API，分散制御・ダイナミックルーチング，グリッド，NFV，IoT，NW及びシステム信頼性，NW及びシステム評価，一般 |
| テーマ（英） | Network software (Software architecture, Middleware), Network application, SOA/SDP, NGN/IMS/API, Distributed control/Dynamic routing, Grid, NFV, IoT, Network/System reliability, Network/System evaluation, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2025-01-NS-NWS |
| 本文の言語 | 日本語 |
| タイトル（和） | 分散型動的グラフにおけるランダムウォーク演算の負荷分散のためのグラフメンテナンス |
| サブタイトル（和） | |
| タイトル（英） | Graph Maintenance for Load Balancing of Random Walk Operations in Distributed Dynamic Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 動的グラフ / Dynamic Graphs |
| キーワード(2)（和/英） | 負荷分散 / Load Balancing |
| キーワード(3)（和/英） | ランダムウォーク / Random Walk |
| キーワード(4)（和/英） | メンテナンス / Maintenance |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 秋元 大河 / Taiga Akimoto / アキモト タイガ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第3著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-01-23 11:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NS |
| 資料番号 | NS2024-172 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.344 |
| ページ範囲 | pp.13-18 |
| ページ数 | 6 |
| 発行日 | 2025-01-16 (NS) |
[研究会発表申込システムのトップページに戻る]