文献

J-GLOBAL ID：202202283405386700   整理番号：22A0969070

G-Thinker:負荷バランスを持つビッググラフにおける認定部分グラフ発見のための一般的分散フレームワーク【JST・京大機械翻訳】

G-thinker: a general distributed framework for finding qualified subgraphs in a big graph with load balancing

著者 (6件)： Yan Da (Department of Computer Science, The University of Alabama at Birmingham, Birmingham, AL, USA) ,  Guo Guimu (Department of Computer Science, The University of Alabama at Birmingham, Birmingham, AL, USA) ,  Khalil Jalal (Department of Computer Science, The University of Alabama at Birmingham, Birmingham, AL, USA) ,  OEzsu M. Tamer (David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada) ,  Ku Wei-Shinn (Department of Computer Science and Software Engineering, Auburn University, Auburn, AL, USA) ,  Lui John C. S. (Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T, Hong Kong)
資料名： VLDB Journal  (VLDB Journal)
巻： 31  号： 2  ページ： 287-320  発行年： 2022年 
JST資料番号： W5017A  ISSN： 1066-8888  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 大きいグラフから,ある条件を満たす部分グラフは,コミュニティ検出や部分グラフマッチングのような多くのアプリケーションにおいて有用である。これらの問題は,高い時間複雑性を持つが,それらをスケールするのを試みる既存のシステムは,実行においてすべてのIO結合である。著者らは,タスクベースの計算モデルを採用する部分グラフ発見アルゴリズムのためにG-thinkerと呼ばれる最初の真のCPU結合分散フレームワークを提案し,また,既存のシリアルアルゴリズムから容易に適応できる分散部分グラフ発見アルゴリズムを書き込むためのユーザフレンドリーな部分グラフ中心頂点引き込みAPIを提供した。クラスタの全CPUコアを利用するために,G-thinker特徴(1)並列タスクアクセスのための高同時頂点キャッシュと(2)高タスクスループットを確実にする軽量タスクスケジューリングアプローチ。これらの設計は,CPUコアのアイドリング時間を最小にするための計算による通信と良く重複する。個々のタスクの作業負荷が偏ったグラフ密度分布により劇的に異なるグラフ上の負荷分散をさらに改善するために,著者らは,処理および分解のために長い走行である傾向があるそれらのタスクのスケジューリングを優先順位付けし,また,長時間運転ストラグラータスクを防止するためのタスク分解のためのタイムアウトメカニズムを提案した。アイデアは,ハイブリッドタスク分解戦略を採用した最大クリーク発見(MCF)のための新規アルゴリズムに統合され,それは,高密度で大きなグラフ上のMCFの実行時間を著しく改善する:このアルゴリズムは,70分における大規模で高密度WikiLinksグラフデータセット上で,サイズ1,109の最大クリークを見つける。大規模な実験は,G-thinkerが,最速の既存の部分グラフ中心システムと比較して,一桁の高速化を達成し,そして,それは,はるかに大きく,そして,より高密度の実ネットワークデータに,よくスケールすることを証明した。G-thinkerは詳細な文書化でオープンソースである。Copyright The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *グラフ ,  スケジューリング ,  著者 ,  アイドリング ,  キャッシュメモリ ,  *部分グラフ ,  クラスタ ,  応用プログラム ,  *発見 ,  計算モデル ,  クリーク
準シソーラス用語： 実行時間 ,  オープンソース ,  最大クリーク , 【Automatic Indexing@JST】

著者キーワード (7件)： グラフマイニング ,  サブグラフ中心 ,  CPU結合 ,  計算集約 ,  クリーク ,  三角形 ,  サブグラフマッチング

分類 (2件)： グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (6件)： 負荷バランス ,  グラフ ,  認定 ,  部分グラフ ,  発見 ,  フレームワーク