Hadoop MapReduce デザインパターン4章〜7章

Hadoop MapReduce デザインパターン ―MapReduceによる大規模テキストデータ処理

Hadoop MapReduce デザインパターン1章〜3章 - n-3104の日記の後編です。

4章　テキスト抽出のための転置インデックスの生成

• Web検索におけるコンテンツの収集（クローリング）、転置インデックスの構築、検索された際の検索結果の抽出（ランキング）の3つについて書かれています。といってもメインは転置インデックスの構築で、あとはおまけでちょっと書いてある感じです。
• Web検索の概要を知らない方はGoogleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)の第1章を読んでおくと読みやすいかもしれません。4-1に転置インデックスについても書かれています。
• 3章で紹介された以下のパターンの利用例が記述されています。
  • value-to-key conversionパターン（擬似コードあり）
    • これ、ドキュメントIDでソートするという要件がなくなるとstripesパターンに言い方が変わるのでしょうか。そういう意味ではstripesパターンとvalue-to-key conversionパターンて似てるのかと思いました。
  • in-mapper-combiningパターン（擬似コードなし）
• 4.5　インデックスの圧縮 についてはよく分からなかったので読み飛ばしてしまいました(^_^;)
• Hadoop MapReduce デザインパターンの4章を読んでみた。 - watawata日記は読んだ方がよいと思います。

5章　グラフのアルゴリズム

• MapReduceによるグラフの並列幅優先探索とPageRankについて書かれています。
  • グラフです。Hadoopやるならグラフは必須と聞いて、ちょっと前から少しずつ勉強してましたが、少しは理解できるようになった気がします。
  • グラフの探索の基本的なところについてはAlgorithms with Python / 集合, グラフ, 経路の探索で私は勉強しました。ちなみに、このページで勉強する前に子象本を読み終えていたりするのですが、まぁ理解していなかったということですね(^_^;)
• まずは並列幅優先探索ですが、こちらについてはLarge-Scale Graph Processing〜Introduction〜(完全版)を見るといいと思います。実際にMapReduceによってどのようにデータが処理されているか図で説明されていてとても分かりやすいです。
  • スライドの前半のSSSPの所です。ちなみに、子象本では距離1ですが、スライドでは距離nで書かれています。
  • あと、子象本で指摘されている毎回グラフをReducerに転送する問題についての対処方法であるShimmy Trickについてもスライドには書いてあります！
  • ちなみに、ダイクストラアルゴリズムについては文系 Hadooper でも分かる Dijkstra アルゴリズム - cocoatomo衝動日記を以前読んで理解しました。
• PageRankについてはもうちょっと数学力？がついてからリトライしようと思います。概要は理解できましたが、すっきりしない感じでした(^_^;)

6章　テキスト処理のためのEMアルゴリズム

• 期待値最大化法（EM）アルゴリズムとMapReduceへの適用について書かれています。
• 撃沈です＼(^o^)／ 色々勉強してから出直します。
  • とりあえず文字だけ追えば雰囲気はつかめました。
  • WEB+DB PRESS Vol.64の特集3の「作って学ぶ日本語入力」も一緒に読むといいかもしれません。ビタビアルゴリズムも紹介されています。

7章　未来に向って

• MapReduceが向かない分野と、その分野に対するフレームワークが紹介されています。

後半まとめ

書いてよかったです。最初に読んだ時は5章はあまり理解できていなかったのですが、今回改めて読んだり調べたりしたお陰で並列幅優先探索について理解できました。

個人的にHadoopが好きなのは、ちゃんとアルゴリズムを扱っている感じがする所です（他にもトレードオフを常に意識させられる点とかミドルウェアっぽい所とか色々ありますけれど）。普段はif文と文字列操作が大半で、せいぜい再帰処理を書くぐらいなので（モデリングやら実装パターンやら色々ありますが）。もちろん、アルゴリズムを使う仕事もあると思うのですが、自分自身にそういう能力がないこともあり、縁遠いなーと思っていた所でHadoopに出会い、とても刺激的で楽しいです。

ちなみに、Hadoopそのものよりも大規模データ処理とか分散データ処理とかそっちに興味があって、その接点としてHadoopがあると言ったほうが適切だったりします。Hadoop自体も細かな部分は変わっていきますし、10年とかのスパンで見れば残っているか分かりませんし。

いずれにしても、こんなにわくわくしながら読んだ本は久しぶりでした。筆者および翻訳者に感謝です。ありがとうございました！