Adding is awesome

One of the Strange Loop 2013 talks where I felt I really learned something useful was "Add ALL the things," presented by Avi Bryant. You can watch a recording here: http://www.infoq.com/presentations/abstract-algebra-analytics. In the video it sounds like his humor is falling flat because you can't hear the audience well, but I assure you there were plenty of chuckles. You may want to download the slides because a couple slides don't show up in the recording starting about 20 minutes into the talk.

He starts by telling us that "adding is awesome" and explains why. But more interestingly, things that we don't normally think of as adding can actually be expressed in ways that are a lot like adding, so they can be awesome too. His focus is on data aggregation: generating statistics from massive amounts of data when you can't actually store all that data.

Heart attack on a Paper Towel, flickr user yogma, CC BY 2.0

Adding is awesome for large data sets because you can partition and distribute addition in arbitrary ways, which makes it very nice for calculating sums in parallel or combining different sums. You only need to hold onto one addend at a time. You don't have to store those addends and reuse them later, so your memory usage is bounded.

There are four specific properties of addition that make it awesome.

1. Binary operation: a + b = c
2. Associative: (a + b) + c = a + (b + c)
3. Commutative: a + b = b + a
4. Has an identity: 0 + a = a

Mathematicians call a set that has an operation with these four properties a commutative monoid.

It turns out that some other non-obvious operations can be expressed as commutative monoids: top N items in a set, average value, and histograms. That means you can do all sorts of awesome things when calculating those on large data sets too.

You can also get approximations for some aggregate calculations using commutative monoids: number of unique values in a set (using the HyperLogLog algorithm), set similarity (Min-Hash algorithm), set membership (Bloom filters), and frequency in a set (Count-min sketch). These algorithms don't give you the exact answer, but they may give you a good enough answer for your large data set.

Are there places where you need aggregate statistics, but an approximate value would be sufficient? I now ask myself that question, knowing that there are some algorithms out there that could give me a more efficient way to get the job done.