文献

J-GLOBAL ID：201702265511902695   整理番号：17A0826168

頂点枝刈りによる大規模グラフにおける高速連結成分計算【Powered by NICT】

Fast Connected Components Computation in Large Graphs by Vertex Pruning

著者 (5件)： Lulli Alessandro (Department of Computer Science, University of Pisa, Pisa, Italy) ,  Carlini Emanuele (Information Science and Technologies Institute “A. Faedo”, National Research Council of Italy, Rome, Italy) ,  Dazzi Patrizio (Information Science and Technologies Institute “A. Faedo”, National Research Council of Italy, Rome, Italy) ,  Lucchese Claudio (Information Science and Technologies Institute “A. Faedo”, National Research Council of Italy, Rome, Italy) ,  Ricci Laura (Department of Computer Science, University of Pisa, Pisa, Italy)
資料名： IEEE Transactions on Parallel and Distributed Systems  (IEEE Transactions on Parallel and Distributed Systems)
巻： 28  号： 3  ページ： 760-773  発行年： 2017年 
JST資料番号： T0882A  ISSN： 1045-9219  CODEN： ITDSEO  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 連結成分グラフ分析を扱う応用における基本的な仕事であり,ソーシャルネットワーク分析,ウェブグラフマイニングと画像処理である。今日のグラフの指数関数的成長により,新しい計算モデルの定義と高分散アーキテクチャ上でのそれらの効率的な処理のためのアルゴリズムを必要とした。本論文では,分解,大規模グラフの連結成分を検出するための効率的な反復MapReduce的なアルゴリズムを提案した。クラッカーの戦略は,木の集合,グラフ中の各連結成分の一つに入力グラフを変換することである。ノードを反復的にグラフから除去し,木に加え,各反復で計算量を減少させる。アルゴリズムの正当性を証明し,その計算コストを評価し,多種多様な人工的および実世界グラフを考慮した包括的な実験的評価を行った。実験結果はクラッカーは交換されるメッセージの全計算時間と体積の観点からの両者の意味で最新技術手法を一貫して上回ることを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 画像処理 ,  アルゴリズム ,  *高速度 ,  CPU時間 ,  指数関数 ,  計算モデル ,  計算量
準シソーラス用語： 計算コスト ,  MapReduce ,  分散アーキテクチャ ,  *連結成分 , 【Automatic Indexing@JST】

分類 (1件)： ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (6件)： 頂点 ,  枝刈り ,  大規模 ,  グラフ ,  連結成分 ,  計算