🚨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

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 🙂

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

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!

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.

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!

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!

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

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.

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.

hi! Interesting to see an animation-only video from you, but you did a great job on 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.

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 like the format! Very different from your usual work, but it felt nicely polished and worked well with the topic.

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!

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

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

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

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

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!

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

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

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.

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

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 ❤

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.

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

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.

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

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

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

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

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.

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 great video and you did a fine job of explaining the concepts behind HLL in simple terms.

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!

Loved the Octarine reference hidden within the Magic Chest explanation.

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

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

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

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

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.

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

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.

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

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

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.

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

Excellent video and animation! You've outdone yourself.

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

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

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

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.

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

Fantastic video! Loving the animations and sound effects. 😄

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!

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

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

Interesting topic and great animation! Love this channel.

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

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.

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.

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

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.

Love your style of explaining and the animations!

Incredibly well explained video. Well done.

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

In videos like these, you should talk more about all of the different applications of the algorithm so that we can understand how it is used

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

Thinking. Say, we have cubes color2 color6 color1 color2 color4 color2 color1, that can be encoded as a set [2, 6, 1, 2, 4, 2, 1]. We don't care about previous colors or all possible colors, we just know the value of each box we've looked through. Then we get a Nth prime number of each value. [3, 13, 2, 3, 7, 3, 2] and sum them together. We get a number 2*2+3*3+1*7+1*13. Not only we can tell by this how many unique values were in a set, but also how many each of them there are. The only problem is how quickly we can get the Nth prime.

My takeaway: It's more simple to create an unindexed list and then check each new input against the current "longest run" hash function, than it is to index a list checking for unique inputs because every new input would require checking all previous inputs, every time. Longest run functions would give you a rough approximation of the number of items in the original list that are unique, based on how much information it ends up taking to describe all of the unique colors. The more unique colors, the more binary information is ultimately needed to express that as a list. Therefore a long run of similar inputs, in your example zero, would require many unique colors to exist.

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

This is one of my favorite algorithms. So clever.

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

those multiple score cards are very necessary, especially for explaining how you can get within 2% accuracy with a scoring system that for a single score card only spits out powers of 2

You're right, this video is different -- but it's fabulous. Well done!

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.

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

THX ALOT i had alot of fun listening and i learned alot :D

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?

This was amazing. Subscribed!

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!

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

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

Such a cool, simple explanation! Loved it

You did a really good job explaining

Probabilistic algorithms are my favourite concept (after recursion of course) There's something so satisfying about doing things randomly, but still getting an acceptable result

Great visualizations! Good work on this video

very good explanation of a very interesting algorithm. great visual aids to help understanding. well done!

Post what you find interesting, I'm sure we will find it interesting. You present and explain topics really well.

Only issue w the hashtables magic chests analogy is that hashtables are pretty efficient w sparse data. They do have a problem with high cardinality but only on existing items, no memory used for non logged colors in this example.

more of this style of concept explanation please!