MrsRF: an efficient MapReduce algorithm for analyzing large collections of evolutionary trees

Suzanne J Matthews and Tiffani L Williams Department of Computer Science and Engineering, Texas A&M University, College Station, TX URL

何をやってるかというと、大量の進化木を比較してそれぞれの間に距離を定義したマトリックスを作ろうとしている。距離の定義は、木をリーフ以外の枝で切断してできた集合を比較することで行う。同じ集合対を与える切断があると１点、と言う具合に加算していく。

でこれを２段のMRでやっている。割にストレートフォワードかもしれない。

Phoenix を使ってる。Phoenixはshared memory の実装なので、注意が必要。

RFは Robinson-Foulds distanceを意味している。OpenMPIも使ってる。

HashRFという方法を改良している。

基本的に進化木の比較に特化して、n^2のマトリクスをハッシュを使って作る。

ローカルにはMapper内部でOpenMPIを使い、グローバルにはMRを使ってハッシュを集計している。