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