MapReduce計算の並列複雑度について(一般)
スポンサーリンク
概要
- 論文の詳細を見る
MapReduceはテラバイト,ペタバイト級のビッグデータを処理するために適した並列計算プラットフォームの1つである。本稿では,MapReduce計算と通常並列計算のモデルとして用いられる組合せ回路の計算能力とを比較することによって,MapReduce計算の並列計算能力が組合せ回路のそれよりも優れていることを示す.具体的には,[7]で提案されたMapReduce計算モデルを用いて,素子数が入力nの多項式で対数多項式時間Tの組合せ回路で解ける問題がMapReduceモデルにおいてO(max(T/lg n, lg lg n))ラウンドで解けることを示す.
- 2013-05-10
著者
関連論文
- 証明書分散問題の近似可能性について
- Population protocolにおけるオラクルをもたない自己安定リーダー選挙問題の可解性に関して
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- P2Pネットワークにおける決定性減衰型ブルームフィルタの提案と検索効率の評価(インターネットの品質評価・品質管理技術,ネットワーク品質,トラヒック計測,一般)
- B-7-80 新世代ネットワークサービス基盤としての仮想化技術のモデル化に関する一考察(B-7. 情報ネットワーク,一般セッション)
- モバイルエージェント間ゴシップの移動計算量について
- 観測に一様な誤差を生じるモデルでの自律分散ロボット群の一点収束について
- 偶数台の自律分散ロボット群に対するリング上での一点集合問題について
- 4台の自律分散ロボット群による正方形形成について
- 動的コンパスを持つロボット群の一点集合問題に対する許容変化量最適なアルゴリズム
- 故障したコンパスを持つ二台の自律分散ロボットに対する一点集合問題の可解性について
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- 極大クリーク分割に基づく自己安定クラスタリングアルゴリズム
- メッセージの確率的な消失を考慮した耐故障合意アルゴリズム
- 相互無関係並列マシンにおける一般化多組織スケジューリング
- MSTに基づくSVMパス追跡を用いた多重多変量2標本検定による遺伝子群解析に関する一考察(IBIS2010(情報論的学習理論ワークショップ))
- 局所グラフカットに基づく高速かつ省メモリな画像セグメンテーション
- マルコフ動的ネットワークにおける通信効率のよいブロードキャストについて
- 分割画像のグラフカットに基づく高速かつ省メモリな画像前景抽出(画像認識,コンピュータビジョン,学生論文)
- 完全マッチング数え上げの高速な指数時間アルゴリズムについて (アルゴリズムと計算理論の新展開)
- 符号理論と完全マッチング計数問題の接点について
- 符号理論と完全マッチング計数問題の接点について
- MapReduce計算の並列複雑度について
- MapReduce計算の並列複雑度について(一般)
- 共通座標系を有しないグリッド平面上におけるファットロボットの集合