| 講演名 | 2020-08-04 分散グラフ管理の連続的拡張とGeneral Replication Factor 尾崎 耀一(慶大), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 集中型の分散グラフ処理におけるグラフの分割ポリシを特徴づける値として，Replication Factor（RF）とEdge Cut（EC）が知られている．RFは枝をキーとして管理する際の頂点の平均複製数であり，ECは頂点をキーとして管理する際の全辺に対する切断された辺の本数の割合である．いずれも，分散的にグラフデータを保存する際の保存グラフデータの重複度合いを示しており，本質的には同一の概念である．一方で，頂点もしくは枝のいずれかをキーとしたグラフ管理が実現できない自律分散型のグラフ管理では，グラフデータの重複保存に関する指標は存在していない．そこで本研究では，RFとECを拡張し，枝と頂点をそれぞれキーとして管理する際の頂点の平均複製数の和を指標General Replication Factor（GRF）として提案する．GRFは，グラフの頂点や辺一方のみをキーにした集中型の管理をグラフの自律分散管理の特殊形態として捉えたものである．評価として，10万頂点・3279万辺のグラフにおいて，自律分散型のグラフ管理を実現する頂点と枝をそれぞれキーにするサーバの混在比率と総サーバ数を変化させながら，GRFの挙動を明らかにした．GRFは混在比率が50%の時に，サーバ数の増加につれてGRFは冪で増加することを確認した． |
| 抄録(英) | Replication Factor (RF) and Edge Cut (EC) are known as values that characterize the graph partitioning policy in centralized distributed graph processing. RF is the average number of replicated vertices when managing edges as a key, and EC is the ratio of cut edges to all when managing vertices as a key. Each of them shows the degree of overlap of the partitioned graph data when the graph data is saved in a distributed manner, and the concept is essentially the same. On the other hand, there is no index for redundant storage of graph data in autonomous decentralized graph management in which graph management using either vertices or branches as a key cannot be realized. Therefore, we propose an index, General Replication Factor (GRF). GRF is an extension of RF and EC. It is a sum of the average number of replications of vertices when managing edges and vertices as keys. Through GRF, centralized distributed graph management can be taken as an extreme example of autonomous decentralized graph management. As an evaluation, we simulated distributed autonomous graph management for a graph of 100,000 vertices and 32.79 million edges by changing the mixture ratio and sum of servers. It was confirmed that when the mixture ratio of servers was 50%, GRF increased in the power as the number of servers increased. |
| キーワード(和) | 自律分散システム / 自律分散グラフ / 分散グラフ管理 / 分散グラフ処理 |
| キーワード(英) | Autonomous distributed system / Autonomous distributed graph / Distributed graph management / Distributed graph processing |
| 資料番号 | IN2020-20 |
| 発行日 | 2020-07-27 (IN) |
| 研究会情報 | |
| 研究会 | IN / CCS |
|---|---|
| 開催期間 | 2020/8/3(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | ネットワークの科学、将来ネットワーク 、クラウド/SDN/仮想化、コンテンツ配信・流通、及び一般 |
| テーマ（英） | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| 委員長氏名（和） | 石田 賢治(広島市大) / 塩川 茂樹(神奈川工科大) |
| 委員長氏名（英） | Kenji Ishida(Hiroshima City Univ.) / Shigeki Shiokawa(Kanagawa Inst. of Tech.) |
| 副委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 浅井 哲也(北大) / 赤井 恵(北大) |
| 副委員長氏名（英） | Kunio Hato(INTERNET MULTIFEED CO.) / Tetsuya Asai(Hokkaido Univ.) / Megumi Akai(Hokkaido Univ.) |
| 幹事氏名（和） | 小畑 博靖(広島市大) / 樫原 俊太郎(KDDI総合研究所) / 谷口 展郎(NTT) / 星野 文学(NTT) / 川喜田 佑介(神奈川工科大) / 中田 一紀(TDK) |
| 幹事氏名（英） | Hiroyasu Obata(Hiroshima City Univ.) / Shuntaro Kashihara(KDDI Research) / Noburo Taniguchi(NTT) / Fumitaka Hoshino(NTT) / Yusuke Kawakita(Kanagawa Inst. of Tech.) / Kazuki Nakada(TDK) |
| 幹事補佐氏名（和） | / 中野 秀洋(東京都市大) / 安東 弘泰(筑波大) / 松原 崇(神戸大) / 眞田 耕輔(三重大学) |
| 幹事補佐氏名（英） | / Hidehiro Nakano(Tokyo City Univ.) / Hiroyasu Ando(Tsukuba Univ.) / Takashi Matsubara(Kobe Univ.) / Kosuke Sanada(Mie Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Complex Communication Sciences |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 分散グラフ管理の連続的拡張とGeneral Replication Factor |
| サブタイトル（和） | |
| タイトル（英） | Continuous Extension of Distributed Graph Management and General Replication Factor |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 自律分散システム / Autonomous distributed system |
| キーワード(2)（和/英） | 自律分散グラフ / Autonomous distributed graph |
| キーワード(3)（和/英） | 分散グラフ管理 / Distributed graph management |
| キーワード(4)（和/英） | 分散グラフ処理 / Distributed graph processing |
| 第 1 著者 氏名（和/英） | 尾崎 耀一 / Yoichi Ozaki |
| 第 1 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 2 著者 氏名（和/英） | 金子 晋丈 / Kunitake Kaneko |
| 第 2 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 発表年月日 | 2020-08-04 |
| 資料番号 | IN2020-20 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | IN-125 |
| ページ範囲 | pp.65-70(IN), |
| ページ数 | 6 |
| 発行日 | 2020-07-27 (IN) |