# What use are groups, monoids, and rings in database computations?

Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github: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: What is Twitter's 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).

-
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
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
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

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...

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

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.

-

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

-

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.

-
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

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.

-

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.

-