Wikipediaの編集履歴を用いた大規模2部グラフのデータストリーム処理

概要

論文の詳細を見る
近年,グラフ構造に対するマイニング技術が注目を集めている.従来の大規模グラフ処理の研究はデータを蓄積して実行するバッチ処理が中心となっているが,リアルタイムな処理が要求される分野も数多く存在し,データを蓄積せずに逐次に実行するデータストリーム処理の併用が求められる.本研究では,バッチ処理を定期実行しつつデータストリーム処理を行うシステムを実装し,大規模 2 部グラフとして Wikipedia の編集履歴を用いて評価した.大規模グラフをリアルタイムで処理するために,ソーシャルネットワークに代表されるグラフの持つ性質であるコミュニティ構造を利用して,いくつかのコミュニティにグラフを分割して処理を行った.結果,4 ノード 48 コアを用いて,頂点数が 207,329 と 1,847,166,エッジ数が 22,034,825 の 2 部グラフを処理し,グラフ分割数に対してデータストリーム処理で 2 乗,バッチ処理で 3 乗の高速化を 30 分割において実現した.その結果,実データの到着レートの約 32 倍の速度でデータストリーム処理することができた.
2011-11-21