MapReduce - t @ wiki

MapReduce

• MapReduceとは
• MapとReduce
• MapReduce応用例

ここを編集

---

MapReduceとは

• MapReduceは
  • 大規模なデータ（1TB．それ以上．）
  • 多数のマシン
  • 効率良く，並列・分散処理するための仕組み

　　「MapReduce：Simplified data processing on large clusters」
　　　Jeffrey Dean & Sanjay Ghemawat
　　　OSDI，2004

---

MapとReduce

• Map
  • データの分解，抽出
  • 例）Webページを受け取って，単語を取り出す．
  • map(key, value) → list<key', value'>
• シャッフル
  • Mapが終わると，同じkeyごとにソートされる．
  • list<key', (value1', value2', value3', ...)>
• Reduce
  • Mapからの出力を集約，計算
  • 例）Mapからの単語情報を，1つのインデックスにまとめ上げる．
  • reduce(key', list<value'>) → list<value''>

---

MapReduce応用例

• 単語カウンタ
• 分散Grep
• URLアクセスカウンタ
• 逆リンクリスト
• 分散Sort
• 転置インデックス

MapReduceのオープンソース版として，Hadoopというものがある．

• Hadoopについて