MapReduce を用いたログ間の依存関係ツリーの抽出アルゴリズムの提案

摘要

ある状態から操作によって別の状態に変化するシステムを考える.同一状態に対して複数の操作種類が存在する場合,状態遷移図はツリー状に繋がり,初期状態の数だけのツリーを構成する.本研究では大量のログデータに含まれる上記を例とするツリーを高速に抽出するアルゴリズムを提案する.大量なログデータの分析には分散処理が有効である.しかし,ツリー構造の抽出にはログ間の関連分析や,関連ログから続く連鎖的な検索処理が必要となるため,処理の分散化が困難であった.提案アルゴリズムではMapReduce でのソート処理を活用し,これらの課題を解決する.