Departmental Bulletin Paper MapReduce 計算の並列複雑さに関する研究

間々田, 剛史

57pp.1 - 7 , 2016-03-24 , 法政大学大学院理工学・工学研究科
MapReduce framework has emerged for processing large-scale data,such as more than a petabyte.Further, a class NC is understood as a class of problems that can perform efficient parallel computation. In this paper, we investigate relationship between NC k+1 (computation time is O(log k+1 n)) and MRC k,which is a class of problems computed by MapReduce with k rounds and we show almost problems in NC k+1 can be computed by MRC k

Number of accesses :  

Other information