文献

J-GLOBAL ID：202202212580663950   整理番号：22A0496663

緩和グラフパターンマッチングのための効率的並列エッジ中心アプローチ【JST・京大機械翻訳】

Efficient parallel edge-centric approach for relaxed graph pattern matching

著者 (6件)： Bouhenni Sarra (Ecole nationale Superieure d’Informatique, Oued Smar, Algerie) ,  Bouhenni Sarra (CERIST, Centre de Recherche sur l’Information Scientifique et Technique, Ben Aknoun, Algerie) ,  Bouhenni Sarra (Universite de Lyon, Lyon, France) ,  Yahiaoui Saied (CERIST, Centre de Recherche sur l’Information Scientifique et Technique, Ben Aknoun, Algerie) ,  Nouali-Taboudjemat Nadia (CERIST, Centre de Recherche sur l’Information Scientifique et Technique, Ben Aknoun, Algerie) ,  Kheddouci Hamamache (Universite de Lyon, Lyon, France)
資料名： Journal of Supercomputing  (Journal of Supercomputing)
巻： 78  号： 2  ページ： 1642-1671  発行年： 2022年 
JST資料番号： T0418A  ISSN： 0920-8542  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 分散グラフのためのグラフシミュレーションに関する事前アルゴリズムは,それらが重いメッセージ通過を示すので,十分にスケーラブルでない。さらに,それらは実世界データに存在する自然スキューによるボトルネックであるグラフ分割品質に依存する。その結果,それらの並列度は制限される。本論文では,分散グラフパターンマッチングのための効率的な並列エッジ中心アプローチを提案した。細粒並列性を可能にし,従って線形スケーラビリティを保証するSTと呼ばれる新しい分散データ構造を設計した。STに基づいて,PGSimと呼ばれる並列グラフシミュレーションアルゴリズムを開発した。さらに,並列で二重シミュレーションを効率的に評価するエッジ中心アルゴリズムであるPDSimを提案した。PDSimは,計算段階を加速するために,分割およびコンバインアプローチでSTとPGSimを結合した。著者らは,大規模なグラフに関する理論的保証と大規模な実験を通して,これらの命題の有効性と効率性を証明した。達成された結果は,著者らのアプローチが1桁以上の既存のアルゴリズムより優れていることを確認した。Copyright The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  シミュレーション ,  データ構造 ,  コンバイン ,  *緩和現象 ,  線形性 ,  命題 ,  有効性 ,  *パターンマッチング ,  並列アルゴリズム ,  ゆがみ
準シソーラス用語： グラフ分割 ,  グラフマッチング , 【Automatic Indexing@JST】

著者キーワード (6件)： グラフパターンマッチング ,  サブグラフマッチング ,  グラフシミュレーション ,  二重シミュレーション ,  大量グラフ ,  並列アルゴリズム

分類 (4件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z) ,  ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (4件)： 緩和 ,  グラフ ,  パターンマッチング ,  エッジ