Parallel Tree Accumulations on MapReduce

DOI PDF Web Site Web Site 参考文献21件 オープンアクセス

書誌事項

公開日
2015-03-20
資源種別
journal article
権利情報
  • http://www.springer.com/tdm
DOI
  • 10.1007/s10766-015-0355-8
公開者
Springer Science and Business Media LLC

この論文をさがす

説明

MapReduce is a remarkable parallel programming model as well as a parallel processing infrastructure for large-scale data processing. Since it is now widely available on cloud environments, developing methodology or patterns for MapReduce programming is important. In particular, XML is the de facto standard for representing data, and processing semi-structured data is involved in many applications. The target computational patterns in this paper are tree accumulations. Tree accumulations are shape-preserving computations over a tree in which values are updated through flows over the tree. We develop BSP algorithms for two tree accumulations as extensions of the BSP algorithm for tree reduction by Kakehi et al. (Tech. Rep. METR 2006-64, Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, 2006). We also implemented the two-superstep algorithms with a single MapReduce execution. Experimental results on a 16-node PC cluster show good speedups of a factor of 10.9---12.7.

収録刊行物

参考文献 (21)*注記

もっと見る

関連プロジェクト

もっと見る

問題の指摘

ページトップへ