MapReduce Patterns, Algorithms, and Use Cases

原文链接 (中文)

• 基本MapReduce模式
  • 计数与求和 # 在mapper里面使用hashmap以及使用combiner来减少传输数据量
  • 整理归类 # 类似倒排索引性质
  • 过滤 (文本查找)，解析和校验 # 每个mapper单独处理
  • 分布式任务执行 # mapper处理小任务使用一个reducer做汇总
  • 排序 # 使用CompositeKey,Group来做扩展
• 非基本MapReduce模式
  • 迭代消息传递 (图处理) # 多轮迭代物化每轮中间结果
  • 值去重 （对唯一项计数） # 扩展排序
  • 互相关
• 用MapReduce表达关系模式
  • 筛选（Selection）
  • 投影（Projection）
  • 合并（Union）
  • 交集（Intersection）
  • 差异（Difference）
  • 分组聚合（GroupBy and Aggregation）
  • 连接（Joining）
    • 分配后连接 （Reduce端连接,排序-合并连接）
    • 复制链接Replicated Join （Mapper端连接, Hash 连接） # 一路数据作为hashmap存放在mapper里面做连接
    • Join Algorithms using Map/Reduce
    • Optimizing Joins in a MapReduce Environment
• reference
  • C. T. Chu et al provides an excellent description of machine learning algorithms for MapReduce in the article Map-Reduce for Machine Learning on Multicore.
  • FFT using MapReduce: http://www.slideshare.net/hortonworks/large-scale-math-with-hadoop-mapreduce
  • MapReduce for integer factorization: http://www.javiertordable.com/files/MapreduceForIntegerFactorization.pdf
  • Matrix multiplication with MapReduce: http://csl.skku.edu/papers/CS-TR-2010-330.pdf and http://www.norstad.org/matrix-multiply/index.html