Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Why would a company like Twitter be interest in algebraic concepts like groups, monoids and rings. https://github.com/twitter/algebird

All I could find is:

Implementations of Monoids for interesting approximation algorithms, such as Bloom filter, HyperLogLog and CountMinSketch. These allow you to think of these sophisticated operations like you might numbers, and add them up in hadoop or online to produce powerful statistics and analytics.

and in another part of the GitHub page:

It was originally developed as part of Scalding's Matrix API, where Matrices had values which are elements of Monoids, Groups, or Rings. Subsequently, it was clear that the code had broader application within Scalding and on other projects within Twitter.

What could this broader application be? within Twitter and for general interest?


It seems like composition aggregations of databases have a monoid-like structure.

Same question on quora: http://www.quora.com/Twitter-1/What-is-Twitters-interest-in-abstract-algebra-with-algebird


I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups. These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say).

share|improve this question
1  
I found this nice article hon HackerNews news.ycombinator.com/item?id=5196708 "the Algebra of Algebraic Data Types" –  john mangual Feb 11 '13 at 2:52
    
The post is a reflection of my thought process :-/ There are maybe a few themes here: github:twitter/algebird, monoid structure of aggregations in database theory, questions about large scale algorithms like bloom-filter, count-min-sketch, general questions about semigroups structures in computer science. Maybe can help me out here? Also keep in mind, I was Math and not CS, so I may be just getting the terms wrong! –  john mangual Feb 11 '13 at 16:16
    
agreed, find it surprising twitter is dinking around in these areas, its rather abstract. the main idea seems to be reusable components for a Mapreduce-like system. algebird seems to have "spun off" from scalding. heres a talk on scalding. however it doesnt mention the algebraic objects. possibly they can be used as data object primitives/types for manipulation in the dataflows, which are also mapped into functional programming style.... –  vzn Feb 11 '13 at 16:49
    
A short exchange with the author of scalding on his algebird library, on Twitter: twitter.com/posco/status/300692719561482240 –  john mangual Feb 11 '13 at 18:14
2  
I would strongly dispute the contention that monoids and semi-groups are both considered 'useless theoretical constructs', as both have quite a bit of utility within mathematics itself as well, both in category theory and for modeling various other algebraic structures. What branch of mathematics do you come from that considers semigroups 'useless'? –  Steven Stadnicki Feb 11 '13 at 21:31

6 Answers 6

up vote 21 down vote accepted

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity).

By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid).

By using Rings, we can do matrix multiplication over things other than numbers (which on occasion we have done).

The algebird project itself (as well as the issue history) pretty clearly explains what is going on here: we are building a lot of algorithms for aggregation of large data sets, and leveraging the structure of the operations gives us a win on the systems side (which is usually the pain point when trying to productionize algorithms on 1000s of nodes).

Solve the systems problems once for any Semigroup/Monoid/Group/Ring, and then you can plug in any algorithm without having to think about Memcache, Hadoop, Storm, etc...

share|improve this answer
    
can someone expand on the link between sparse matrices & zeros in some Monoid? –  vzn Feb 12 '13 at 0:09

One important problem in distributed file systems (DFS) is to generate files from distributed blocks. The area of Erasure code from information theory and Algebra (groups, rings, linear algebra,...) is used extensively in distributed fault tolerant file systems for example in HDFS RAID (Hadoop Based File System). Social network and Cloud companies are extensively based on DFS, so they need people who are master in Algebra and Erasure Code to design better and high performance systems (like Reed-Solomon codes, etc).

This is also good poster for their application (algebra) in cloud storage: Novel Codes for Cloud Storage

share|improve this answer

Monoids are ubiquitous in programming, just that most programmers don't know about them.

  • Number operations like addition and multiplication.
  • Matrix multiplication.
  • Basically all collection-like data structures form monoids, where the monoidal operation is concatenation or union. This includes lists, sets, maps of keys to values, various kinds of trees etc.
  • For a given type $A$ functions $A\to A$ together with the identity function on $A$ form $A$'s endomorphism monoid.

Some other operations don't form monoids but semi-groups. A good example is searching for the minimal element of a sequence of elements: $a\cdot b$ represents the minimum of $a$ and $b$ wrt some given ordering.

Because monoids are so general, they allow to write very generic functions. For example, folding over a data structure can be expressed as mapping every its element to a monoid and then using the monoidal operation to combine them to a single result.

Another nice and very general example is the generalization of exponentiation by squaring to monoids (or semi-groups). We can write a single function that computes $\underbrace{a\cdot\ldots\cdot a}_{n-\mbox{times}}$ only in $O(\log n)$ operations. Applying it to different monoids we get:

  • fast exponentiation of numbers;
  • fast exponentiation of matrices (this can be used to compute Fibonacci numbers in $O(\log n)$ multiplications);
  • fast method for building large finger trees, as appending one element takes $O(1)$ time but merging 2 trees takes $O(\log(\min(n_1,n_2)))$.
  • etc.

For more examples see Examples of monoids/semigroups in programming.

share|improve this answer

The set of all words over some finite alphabet together with concatenation forms the free monoid $(\Sigma^*, \cdot)$. Therefore, the whole field of formal language can be viewed through the algebraic lense, and it is sometimes taught like this.

In return, considerations on formal languages have yielded the Earley parser which can be extend to parse on semirings. This is useful in natural language processing and other areas using stochastic models for (formal) languages.

share|improve this answer

If your question is

What are examples of groups, monoids, and rings in computation?

then one example I can think of off-hand is for path-finding algorithms in graph-theory. If we define a semiring with $+$ as $\min$ and $\cdot$ as $+$, then we can use matrix multiplication with the adjacency matrix to find all-pairs-shortest-path. This method is actually described in CLRS.

While this may seem only theoretical from an algebraic perspective it allows us to utilize very heavily optimized linear algebra libraries for graph problems. Combinatorial BLAS is one such library.

share|improve this answer
1  
Yep, and we added minplus to do just that: github.com/twitter/algebird/blob/develop/algebird-core/src/main/… –  Oscar Boykin Feb 11 '13 at 18:32

I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups. These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say).

There is rather too much interesting to say. However, it's more a topic of discrete math and combinatorics than for abstract algebra and analysis, at least for the less trivial topics. There is also the question how much you have to know about a certain topic before you can tell somebody else it would be an interesting mathematical topic related to monoids and semigroups. For example, I find the following topics (related to semigroups) interesting:

  • finite semigroups and Krohn-Rhodes theory
  • partial symmetries, inverse semigroups, groupoids and quasicrystals
  • semirings and tropical geometry
  • partial orders and Möbius functions
  • submodular functions and (Dulmage-Mendelsohn like) decompositions

Do I know much about each of these topics? Probably not. There are also many more mathematical topics related to monoids and semigroups, some of them are more internal to semigroup theory itself (like Green's relations), others are more general and not specific to semigroups (universal semigroups, homomorphism and isomorphism theorems, quotient structures and congruences), but also important from a mathematical point of view. The topics I did cite above mostly have "real world" applications, but there are more related topics that also have "real world" applications.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.