2024-03-29T04:46:50Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000917852023-04-27T10:00:04Z01164:02592:07086:07157
On parallel complexity of MapReduce computationMapReduce計算の並列複雑度についてenghttp://id.nii.ac.jp/1001/00091769/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=91785&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Institute of Electronics, Information and Communication EngineersThis SIG report is only available to those in membership of the SIG.法政大学理工学部名古屋工業大学大学院工学研究科和田, 幸一泉, 泰介MapReduceはテラバイト,ペタバイト級のビッグデータを処理するために適した並列計算プラットフォームの1つである.本稿では,MapReduce計算と通常並列計算のモデルとして用いられる組合せ回路の計算能力とを比較することによって,MapReduce計算の並列計算能力が組合せ回路のそれよりも優れていることを示す.具体的には,[7]で提案されたMapReduce計算モデルを用いて,素子数が入力 n の多項式で対数多項式時間Tの組合せ回路で解ける問題がMapReduceモデルにおいてO(max(T/log n, lg lg n))ラウンドで解けることを示す.MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing big data on tera- and peta-byte scale. In this paper, we study the MapReduce framework from a standpoint of parallel algorithmic power by comparing Mapreduce computation with combinatorial Boolean circuits usually used in parallel computation. In a theoretical MapReduce model which is an extended one proposed in [7], we show that any problem solved by a Boolean circuit with polynomial number of gates and polylogarithmic time T can be solved by MapReduce computation with adding a bit of extra memory to the amount of memory denoting the Boolean circuit in O(max(T/lg n,lg lg n)) rounds, where n is the input size. That is, MapReduce computation can accelerate the number of rounds by almost lg n of the computation time of the circuit.AN1009593X研究報告アルゴリズム(AL)2013-AL-14422152013-05-102013-04-24