HackerPapers

arXiv:1304.7544cs.DC

Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms

Jimmy Lin

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

It is well known that since the sort/shuffle stage in MapReduce is costly, local aggregation is one important principle to designing efficient algorithms. This short paper represents an attempt to more clearly articulate this design principle in terms of monoids, which generalizes the use of combiners and the in-mapper combining pattern.

arXiv comments
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing cs.DBDatabases cs.PLProgramming Languages

On Hacker News

Linked by 1 identifiable commenter in 2 comments across 2 threads, from Jul 2016 to Jun 2018.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Notes on Discrete Mathematics (2017) [pdf] 1 comment

    • You might see the value of knowing some abstract algebra in "Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms" https://arxiv.org/abs/1304.7544 In general, if you can model a distributed or concurrent system in terms of a monoid (or better, a…

      noelwelshView on HNParent context

  2. Algebraic patterns – Semigroup 1 comment

    • Yeah, the application section is pretty poor. The number one large-scale practical application of semigroups (and, more often, their extension the monoid) is in parallel and concurrent systems. Associativity says that order of operations doesn't matter, which in turn implies you…

      noelwelshView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.