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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

---

The above is not an answer to the real question, but only addresses the "... are normally considered useless theoretical constructs ... for lack of anything interesting to say ..." remark. So I listed some "interesting" points, claimed that those mostly have "real world" applications, and now Hi-Angel requests a bit of info about those applications. But because "there is rather too much interesting to say," don't expect too much from that info: The Krohn-Rhodes theorem is a decomposition theorem for finite semigroups. Its applications involve the interpretation of the wreath product as a sort of composition (of transducers) in connection with the theory of automata and regular languages, and occurs in the classification of regular languages using pseudovarieties. Mark V Lawson: two tutorial lectures and background material contained (404 now) good material on Inverse Semigroups. The basis for their applications are their connection to the symmetric inverse semigroup, i.e. the set of all partial bijections on a set. One can also start with basic algebraic characterizations of inverse semigroups, but this approach risks to neglect the connections to partial orders which are important for many applications. Some day I will have to blog about a specific application of inverse semigroups as "hierarchy" used to compress semiconductor layouts. Applications of semirings have already been described in the other answers (and tropical geometry would take us far from computer science). Because monoids and semigroups are also related to partial orders, such nice topics like Möbius functions as described in Combinatorics: The Rota Way are also related. And then also topics from Matrices and Matroids for System Analysis like the Dulmage-Mendelsohn decomposition become related, which were one of my motivations to study lattice theory (and hidden hierarchical structures).