BT

最新技術を追い求めるデベロッパのための情報コミュニティ

寄稿

Topics

地域を選ぶ

InfoQ ホームページ ニュース MapReduce パターンとアルゴリズム,ユースケース

MapReduce パターンとアルゴリズム,ユースケース

ブックマーク

原文(投稿日:2012/02/08)へのリンク

Hadoop と ビッグデータ利用の爆発的な増加が示すように,多くの人々が今,既存のシステムを MapReduce に転換するためのアプローチを模索している。しかし MapReduce の実装設計を取り上げた出版物は,"Data-Intensive Text Processing with MapReduce""Mahout in Action" という特筆に値する例外を除けば,残念ながら皆無に等しいのが現状だ。そのような中,Ilya Katsov 氏が自身の新しい記事 "MapReduce Patterns, Algorithms, and Use Cases" で,MapReduce フレームワークの適用によって解決可能な問題についての系統的な概説を行っている。

最初に取り上げているのは,汎用並列実行フレームワークとしての MapReduce の比較的簡単な利用方法である。物理学的および工学的なシミュレーションや数値解析,あるいはパフォーマンス試験といった,巨大クラスタの活用を必要とする計算集約型およびデータ集約型処理の多くに適用可能なものだ。その次は計数や集計,(特定機能に基づく) データ照合,フィルタリング,分析,評価,ソートなどといった,ログ解析や ETL,データ照会などで一般的に使用される一連のアルゴリズムである。

MapResuce パターンの2つめの大きなグループとして氏が論じているのは,複数のリレーショナル MapReduce パターンなど,データウェアハウスアプリケーションで頻繁に用いられるものだ。Hive と Pig という2つの実装で広く活用されているこれらのパターンには,述語/関数ベースのデータ選択やデータ投影,データの和・差・積,groupBy集計などが含まれている。これとは別に,データ結合の実装に話題を限定した議論があり,リパーティション結合 (repartition join) やレプリケート結合 (replicated join) などのアルゴリズムが論じられている。

記事は複雑性の連鎖をさらに昇って,グラフ解析や Web インデックス,一般的な検索アプリケーションなどで利用されるグラフ処理や検索アルゴリズム (幅優先検索),ページランクとデータ集約アルゴリズムなど,より複雑な MapReduce 処理アルゴリズムについても議論している。相互相関の計算を必要とするユースケースとしては,一般的なテキスト分析や市場分析も話題としている。ここでは "ペア" と "ストライプ" という2つのデザインパターンと,そのメリットの比較も行っている。

Katsov 氏が最後に提供しているのは,機械学習の分野でのさらに複雑な MapReduce 適用に関する,優れた参考文献である。

記事で取り上げているアルゴリズムの多くには擬似コードとその適用性,長所と短所,現実でのユースケースに関する基本的情報も提供されている。

現在も多くの人々が,自らのビジネス問題の解決に対する Hadoop と MapReduce の適用性に苦慮している。いまだにそれを "ビジネス上の問題を求める技術的アプローチ" と解釈する向きも一部にはある。この記事はMapReduce アルゴリズムとユースケース,そしてデザインパターンの間に存在する空隙を埋める重要なステップであり,悪名高い "ワードカウント" をはるかに超越する MapReduce の能力と,実用的な問題を幅広く解決するためにそれを活用する方法を示すものだ。

この記事に星をつける

おすすめ度
スタイル

BT