🚨The Nitty Gritty Details🚨 Seems folks were interested after all! 😅 - "Linear counting": HLL struggles when there isn't much data / the cardinality is low (the large granularity of 2^n when n is a small number means relative error can be quite high). Most implementations use a "linear counting" scheme under a certain threshold, typically a sorted list or hashmap. Up to the threshold, counts are recorded accurately in that datastructure. When the threshold is reached (say, 50000 unique elements) the counts are replayed into an HLL and it starts estimating from then on. If the implementation is good, it can often reuse the same segment of memory to avoid re-allocating too - "++ in HLL++": these are some empirical constants and a few other tweaks that Google added to the algorithm, which help smooth out the relative error (particularly at small and very large cardinalities) - The size of an HLL sketch varies by implementation, but typically on the order of a few kilobytes up to a few hundred kb at the most. Very compact! If the scorecards/registers are compressed, that means there are tens of thousands of scorecards tracking the runs. - In contrast, a hashmap/set could be many orders of magnitude larger. Suppose you have 500m unique 64bit integers. That ends up being 500m * 8byte = 4gb of memory. Multiply that by 10-100 partitions (not uncommon for advanced reports) and 10-50 instances from multiple servers... you are quickly looking at hundreds of gb of datastructure to transfer, store on disk, page into memory for iterative processing/merging. And that's just the keys alone, ignoring the overhead of the map/set itself. There are tricks to reduce this (shared global dictionaries, memory mapped files, etc) but none are free and they are all more expensive than a HLL sketch! - Yes, I know hashmaps don't actually allocate all that memory up front. But that was an easier layperson explanation than digging into how loading factors, collision resolution and re-allocations work 😉 I wanted to convey that hashmaps trade space for performance, hence the analogy. But it should be noted that even with a modest 0.7 loading factor, unless you vastly over-allocate the map you will eat a lot of performance due to memory re-allocations when trying to use it for very large cardinality datasets. And it's made worse by the merge cost on a reduction node. So the analogy isn't that far off! - HLL is fast! It may seem like a lot of work, but modern (non-cryptographic) hash functions are highly optimized. And most processors have built-in instructions to count leading or trailing ones/zeros (en.wikipedia.org/wiki/Find_first_set). So in practice, HLL will have about the same runtime cost as a hashmap/set but doesn't need to deal with memory re-allocations. And it's vastly faster than any sorted list/set approach. - HLL is best suited in an environment where you expect millions of unique elements, spread over a dataset on multiple servers (in terabytes+ of data). If all your data fits on one machine, it's much faster/easier/better to just count it exactly. 🙂 - The cardinality metric seems pretty boring, but ends up being super useful at-scale! The distinct count of session IDs, IP addresses, src-dst tuples, etc partitioned by a few different criteria. Very useful for reporting, analytics and forensic style investigations. - The hash function ("transmogrifier") really isn't that important, as long as it's considered a good hash (good pseudorandom output) and fast. Something like murmurhash is often used, with 64 or 128bit outputs. - HLLs "merge" by taking the maximum run from each respective scorecard. So if you have two sketches that have scorecards [1, 10, 5, 3] and [3, 3, 4, 5] the merged result would be [3, 10, 5, 5]. The maximum operation is commutative (max(a,b) == max(b,a)) and associative (max(a, max(b,c)) == max(max(a,b), c)) so we can just take the max of all values for a specific scorecard slot and it's equivalent to having run the algorithm on all the data serially instead of in parallel.

This feels like such an "outside the box" cheat, instead of counting the different colours, just find the rarest one and workout how likely/unlikely it is to be in your set. I love it

- That's such a cool algorithm, especially the fact that it can be run asynchronously. - Thanks for including the programming concept names in the corner, it really helps me understand at a more concrete level. - I would love to see more animated videos or segments to help explain concepts. - If you haven't already, this video would make a perfect submission to the Summer of Math Exposition competition.

Explaining hash tables as "magic chests" is very cute but surprisingly accurate.

Hope the animated format wasn't too disconcerting considering the usual content on the channel! 🤞 I originally filmed this on a whiteboard, but it was hard to see the details and ended up being pretty boring. Figured I'd take a crack at hand-animating instead. Probably won't be a regular occurrence on the channel (too much work!) but was a fun diversion from the usual stuff 🙂

I really like how you describe programming terms in ways that non programmers can easily understand, also putting the actual names of them in the corner was a very nice solution to clarify what you were talking about to us programmers

This video was soo well done! I love the way you visualized the nature of how HashMaps and Large Scale computing feel - the idea of using the stack of blocks up into the clouds including sound effects for it makes it so visceral - wow, we need more of this to teach people about computing!

I use HLL all the time at work and this is such a clear and concise explanation of how it works. Also love the animation format. Thank you for putting the video together!

The hash function is very important here, it is a non-trivial topic itself. Also, it would be nice to mention some practical real-world uses of this algorithm.

Wow. I’m actually taking a scary Uni course called “algorithms for summarizing big data”. We’ve learned a variant of the algorithm you showed, but you made it orders of magnitude clearer. Thank you!

The information was laid out in such a clear way, I was able to effortlessly follow and even be a couple of steps ahead at some points. Good stuff.

Missed opportunity. One of the cubes should have been a Portal companion cube.

I like the format! Very different from your usual work, but it felt nicely polished and worked well with the topic.

This reminds me a lot of weighted reservoir sampling, especially in how you can run the algorithm in parallel and then combine the results. Instead of combining scorecards, you combine the total weights and chosen samples according to their probability. This allows you to sample a very large list of candidates with a uniform (or custom!) probability distribution.

I love your description of this. I've watched your hardware / instrument related videos for years, which I learned from but did not start out with the understanding I did on this one. Very impressed with your ability to break difficult subjects down clearly, and I've been leading development both in and out of companies for decades. I'm now lead dev for a large, unlimited scale, open decentralized network that will use this for some powerful applications over time. Now, I have a great explainer to point people to in order to understand it :) We've got some projects in progress that could definitely use your help and possible cooperation in exchange for strong support of your efforts. You clearly have no lack of pursuits, but I'd be happy to have a discussion about it.

This is cool because the video can explain the algorithm to people who are beginning programmers, people who have taken a few coding classes (with the function/algorithm names in the right), and experienced programmers with the sources at the end.

hi! Interesting to see an animation-only video from you, but you did a great job on it!

This is not a video I expected from your channel but I love it! I like videos like this because they give me ideas for projects, implementing this algorithm with a practical use should be fun :)

The narration and animated diagrams were incredibly helpful in a basic understanding of something i would never even begin to grasp reading that paper. Top tier content as always!

I'm glad I saw a short of yours so I could come back and watch everything I've missed.

I’m not much of a computer or algorithm person, I’ve always worked with my hands, but this video really impressed me. I understand the concept and appreciate how elegant a solution it is! Once I visualise cubes or coins, my brain that works in 3D rather than abstraction, seems to latch onto the concept easily. Great vid sir!

Omg this is amazing!! The animation is so stylish I love it! Thanks for giving something new a go - but I can’t wait for the next materials video! Doing materials at uni next year and your content has gotten me so excited and informed for it. ❤

Please make more of these! I like this format and you have always been an exciting teacher!

I love that you put a note at the bottom stating the concept you are explaining, so I can immediately figure out what it is exactly that you are trying to explain instead of trying to guess it from the explanation.

I love it! I also worked a lot with probabilistic structures, and it was such a surprise when I found out that hyper log log just counts zeros to do it's magic xD But I mostly worked with min-hash tables and bloom filters. They are nice for getting similarity of groups ^^

This was way more interesting than I expected heading into the video. The animation was great! I know the example used in this was unique colors, but as someone clueless to programming, I'm curious how this is used in real world applications.

Your videos are always amazing! But this one is unique, incredible. But also hope you don't stop with the former format, cause those both are sooo good!

Love how you took time to animate all of this! Gives a unique style to your videos

I just understood HLL in less than 10 minutes, a concept I struggled to understand for more than 2 years. Your explanation is phenomenal!

This guy leans so hard into the "programming-as-wizardry" metaphor that his cubes can be the color of magic. Pratchett would be proud.

I wasn't expecting any of my fevorite programming/math related channels to cover HLL, And it ended up covered in the nicest way by the most unexpected but another one of my favourite channel, Thanks for this, It was a treat ❤

I've not seen your videos before but I absolutely love the way you've explained this and it's uses. Fun animation too!

Definitely interesting algorithm but I think it only has use in scenarios where the cardinality is huge. Anything with order of magnitude less than millions can be counted exactly. For billions and above, this algorithm really makes sense.

A wonderful video! It felt very manageable, without simplifying the problem into insignificance(I think, maybe I should try to go implement it and see...) The little notes for the programmers were especially nice, made it clearer what was actually going on very quickly for those who care and therefore are pretty likely to know what a hash is, without sacrificing intuitiveness

This has helped me understand how data search optimization must work. I always wondered how SQL engines estimated cardinality in developing an execution plan. I see how the hash fits in now. Thanks for a very compelling video.

This was a great video and you did a fine job of explaining the concepts behind HLL in simple terms.

it’s different but my first guess of how it works is a method i saw talked about for estimating the total number of species. you basically look at the new ones you find over time and as that reduces, you can then estimate how many are left. and the selecting which “scorecard” to put it on might be a little faster than the idea i had before that was mentioned of generating multiple hashes for each color, considering them separately, and at the end, taking the min, but maybe harmonic mean would still be better. it might be more accurate, but if the hash is slow, it would be slower because you would need to do it several times or more.

This was a really good video, I liked the visuals, even if it was different from your usual content. Learning is learning, and that is great.

Amazing video! I love how the core of the video is very simple but you still put the nitty gritty details in the bottom left corner, its a great way to address a diverse audience :)

2:32 Octarine. I approve of this reference. 🙂 (And 42 shortly after. lol)

2:46 That is _not_ the problem with hash maps. They can actually be quite space-efficient.

This is a really well made video, I dont know a whole lot about programming but the animation visuals and the good explanation helped me a lot!

I love your channel and the videos you make. It's always a highlight to see new videos appearing.

Interesting video but I would have liked to see a bit more on how this algorithm is used on in practice.

6 years of watching math UKposts and I've never seen this. Great rundown and very straightforward animation

Fantastic video! Loving the animations and sound effects. 😄

Love the animation style! Im glad i clicked on this video. You did a great job of breaking down and explaining this topic

So cool! More videoes like this please 😊

This is an amazing video, and a perfect “ah-ha centered” explanation. One critique though is when using colors to distinguish things it always helps to superimpose a symbol of some kind for accessibility reasons.

The content is great and really interesting, but I love your graphics design on this as well. This is really nicely explained, graphically.

Super interesting vid bud, keep up with the good work. Waiting for more algorithm videos in the future ;)

Damn, was just about to click away, but then you told me not to. Now I'm a sub. 😢

This was amazing. Subscribed!

This is a fantastic and highly engaging, interesting video. Keep up the awesome work, look forward to seeing more like this.

Loved the format and animation. Very cool subject. Happy to learn about it!

extremely useful video, and it showcases a very powerful concept that shows up in modern problem solving. Sometimes getting the exact perfect answer is extremely hard and expensive either time wise or resource wise. However, there can be clever approaches that either get you an answer for a simpler problem that is good enough, or (like this one) gives you a close enough answer to the same problem.

That’s such a beautiful algorithm with such a wonderful presentation. Thank you for sharing this. I think this way of presenting is highly accessible. People who understand can extrapolate the larger concepts and people who don’t get a chance to understand.

I have been asked on an tech interview about how to solve approximate distinct count on large random events in a near-real time context for a data engineering position. Hyper log log was the solution expected but never heard of it. I learned with this video for the next time :)

The machining and nano stuff videos are amazing, but I'm pretty sure the kinds of people into both of those will have a healthy interest in algorithms and computers. Great stuff!

Great video/explanation. My first real project when I started at google a few years ago was to do an HLL implementation and this was a great nostalgia trip for me. I'd never heard of it when I was given the project so I first had to learn the basics of HLL, and then go and learn a bunch of implementation specific details that complicated it.

This was a wonderful topic, graphics, and presentation...thanks!

Love your style of explaining and the animations!

Interesting topic and great animation! Love this channel.

I was thinking of something a bit similar to handle floating point calculations on vastly different numbers. Adding a very small number to a very big number - so different the small number would fall through, below the least significant digit of the big number - change it to a chance. Like, if you'd need 10,000*Smol to increment the least signifant digit of Big, each addition of Smol has 1 in 10,000 chance to do it alone.

It was a nice change of pace, thanks for the snazzy explanation.

Excellent video and animation! You've outdone yourself.

This is so well explained! Even for me as a programmer it is better to hear about it in a easier way.

That was a very clear presentation and your animations are great!

Loved the Octarine reference hidden within the Magic Chest explanation.

This was amazing. Please do more :))

I had an exam inspired by Flajolet work once. It consisted on deriving a PDE from a combinatorial problem to then use series to get probabilities. One of the most interesting exam of my life !

Incredibly well explained video. Well done.

Great visualizations! Good work on this video

Some mad After effects skills here. Amazing work.

An important point to note about HLL: don't use it if there's any possibility of adversarial inputs! This is for two reasons. For one, an adversary can produce inputs that artificially inflate the resulting count. This is fairly straightforward if the hash function used is not cryptographically strong - just generate inputs whose hashes end in . (Redis, for instance, uses MurmurHash64A... which is a great hash in many ways, but is _not_ cryptographically secure.) Less obviously, this is still relatively straightforward even if the hash function is strong. The attacker can just generate N values, run them through the same HLL algorithm you're using, and send you only the item that scores highest in each bucket. (Of course, this requires O(n) work on the part of the attacker.) This results in each of said M items appearing as though they were worth N/M each, on average. You can work around this by using an HMAC with a secure (and secret!) key, but this is seldom done as it is costly for performance. (And there is no way to rekey if said key is compromised, either.) Another issue is that HLL is great for timing attacks. By which I mean, it is rather awful against timing attacks. For one because of the conditional update. (This part can be replaced with an unconditional writeback with a CSEL or similar... however this loses one of the attractive properties of HLLs, namely that actual writes to the HLL tend to be fairly infrequent, so you can share a single HLL across multiple cores very easily with relatively little contention.) And for another because it's essentially indexing into an array with a hash of the input object, so an adversary who can add inputs can often e.g. detect that no-one has added X recently. (...or anything else that hashes into any buckets in said cache line. It's not perfect.)

Oh neat! I've used this via Apache Druid which implements the Apache Datasketches implementation of this. Thank you for the explanation!

Excellent video. The process I employ intuitively trying to solve your colorful block problem is practically identical to the algorithmic development you are trying to reveal. I suspect you would (or do!) very much enjoy what's called the german tank problem. It feels adjacent to this, in a way.

an unexpected style and topic from your channel i love it, do more!

This is awesome content! Keep it up!

I loved the way you explained such a hard thing with a very understandable way

You did a really good job explaining

absolutely love this video. super interesting topic, super stylishly done, really great some3 entry. also an appearance in the wild of the harmonic mean, the most underused mean

I found a flaw in this algorithm. It assumes that the data set being inputted has been evenly randomised. It will not work if there are, say, 1000 blue cubes in the data set at the beginning, and then after the 1000th cube other variations begin to appear. So you would have to scramble your data before feeding it in the algo

This feels like drawing a circle inside a square, then counting the number of dots inside the circle vs the square, to estimate PI

It wasn't until I recognized the voice that I even realized what channel I was watching. An interesting departure from your usual videos, but I liked it. It fit the subject matter well.

more of this style of concept explanation please!

That adjustable precision also allows for anonymization

It sounds helpful if you don't need absolute precision in a search result, which for something like decisions in/for a social media algorithm, you don't - you just need a good idea of the figure. Your input data will be massive and constantly changing, so a precise value will be inaccurate by the same tolerance of error pretty quickly. Typing from an hpc perspective, as you're allowing parallel processing anyway, it sounds like it'd be a lot quicker to just merge multiple stacks via a binary tree. If you want to reduce the amount of parallism at the cost of speed, increase the iterations of stacking: Merging the results will be near-instantaneous afterall, and you don't even need traditional processors for the merge.

Awesome video! You should make one on Bloom Filters next. Those also blew my mind when I first learned about them.

I LOVE THIS VIDEO!! Killer work, thank you so so much!

It might not be your usual style of video, but it got me to subscribe! I'm aware that animation is too costly on youtube, takes too long and the algorithm punishes the lack of updates, but you could probably do the video with some props instead for quicker recording and gain most of the benefits. Or just cheat a bit with it, there's plenty of ways to do that, and more coming out with AI tools I imagine.

Thanks, this was very new to me! I would love a part 2 that talks about applications and maybe also an implementation. Are there any physics related problems that can be solved by this?

Never heard of this algorithm before, but you explained it so well I think I could code it easily. Nicely done! The only part I had to watch twice was the merging of two score cards. So the union of two scores A and B is just the max element of that slot, right? U = {max(A[0], B[0]), max(A[1], B[1]), ... }

Such a cool, simple explanation! Loved it

I am a developer and had never heard about this, and I love it! I am probably going to research more about it and I'll try to implement it as a fun project.

Hey great video, I really liked the animation style. This is my fist time hearing about this algorithm and having a visual representation helps a lot. Got one question about collisions, does the algorithm have a way to deal with binary secuences that finish with the same or less 0's (other than having multiple counters), or those cases are not probabilistically relevant enough to be taken in consideration?

I love these styles of videos! I’m not currently a programmer, but I want to be! This was so fascinating and you do such a good job at explaining and illustrating what you’re trying to get across! Please I NEED more!

Wow so glad you made a video for SoME3!! Unexpected given your other videos but pleasantly surprised! Nice video :)

I love the animation, as a software engineer - it's sooo on point well done!

Chapters: 0:00 Introduction to the problem: new HashSet(collection).size() 1:09 Unsorted list, linear traversal 2:18 HashSet 3:02 HyperLogLog 7:16 Precision / Memory Usage / Stability 8:21 Parallelization 10:39 Ad ;)