A problem so hard even Google relies on Random Chance

[@BreakingTaps]

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

[@Splarkszter]

Quite amazing thing. Super helpful to keep in mind for the future!!!

[@iwersonsch5131]

Now what if you have like 10^20 buckets and then build a stack in each bucket? That avoids having to allocate much space, and it avoids getting high stacks that are long to search through

[@Rin-qj7zt]

this is a fantastic video with good explanation techniques, but I think you need to clarify more about why exactly this is useful. sure, you can merge cardinality between different computers a lot faster. _why is that useful?_ what i mean is, if so many companies are using this, _what are their programs accomplishing?_

[@BreakingTaps]

@@Rin-qj7zt The short answer is "reporting and analytics", the longer answer is hard to pin down since it's used for a ton of different purposes. But imagine something like "Show me the number of unique session IDs in our game, from the last year, partitioned by tuple". That sort of report could span literally billions of "game event" rows in the database, and generate dozens or hundreds of "buckets" representing each tuple combination. And inside each bucket there's a count of unique session IDs which are proxies for users/gamers sessions Then it's all thrown onto a realtime dashboard in an office, fed into a realtime algorithm for scaling the game servers, or a PDF report for management, or off to marketing/sales/whatever.

[@Peter_Enis]

@@iwersonsch5131 first thing I thought of.... The set grows (and gets slower) but should make for an accurate answer?

[@bjarnivalur6330]

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

[@snared_]

This is the core essence of it.

[@XerosOfficial]

@_Karlsson It is used in some applications to estimate how much memory you need to allocate, then you can use another algorithm, such as the "magic chest" one he referenced in this video to get exact value, but without requiring nearly as much space.

[@KatherynneF]

@_Karlsson Breaking Taps described at the beginning how this is used for real world applications. Coding problems aren't math problems, so answering the motivating problem is much more important than answering the theoretical analogy exactly.

[@slaapt]

That's always an issue with examples. Either they are trivial and don't properly show how stuff works for more complex variants, or they don't fit the question asked. No, the algorithm doesn't solve the question asked in the beginning, but the question was intended for people to be able to follow the explanation. An actual use case would be of such technical complexity that the current runtime of the video would be used to explain the problem rather than explaining the solution.

[@absurdengineering]

Thing is: surprisingly often, knowing exactly isn’t necessary even though at first glance it appears so. Many other algorithms predate this and they did not anticipate probabilistic cardinality determination. There has been plenty of work on figuring out how to adapt other things to use this approach. It was borne out of a real need, but that need needn’t be the only one. Once you know what you didn’t know, the perspective changes.

[@BreakingTaps]

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 🙂

[@Scyth3934]

Nope! I'm just fine with it

[@Yenrabbit]

Really great, thanks for sharing!

[@vegasu9418]

nice vid! ever going to try to beat Sam Zeloof at higher res transistor fabrication?

[@Dinnye01]

It's perfectly fine. I'll consume your content no matter what.

[@MrBeaach]

consider entering this video into the SoME3 competition,

[@decb.7959]

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

[@ColinTimmins]

I hope they do more as well. I can only learn visually as I am very dyslexic. ChatGPT has become invaluable to me as it “erases” errors and I can manipulate data in a way that was not possible before. 😊

[@peraltarockets]

@@ColinTimmins ChatGPT makes things up because it's just a fancy regression model. Please do not use it for data analysis.

[@cheesebusiness]

“asynchronously” Probably you meant “in parallel”

[@sausas8209]

@@cheesebusiness tHreAdEd

[@mrbrianakias1]

​@@cheesebusinessit's a programming term

[@pafnutiytheartist]

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

[@phizc]

Agree. Only thing missing in the description is that the chest will only store 1 of each. Which is perfectly fine for counting distinct items, of course.

[@pafnutiytheartist]

@@phizc There are modifications allowing you to store multiple items in case of hash collision, python dicts is one exhample. It has a speed and memory penalty but still has a lot of applications.

[@PattyManatty]

As described it's more of a hash set than a hash map/table. But of course the fundamentals are the same

[@kgoblin5084]

It's a good analogy, although I do think it could be improved, as parts of it were a bit outright misleading on how hashsets work: 1. the shelf has a 'warm colors' side, where the red & orange shelves are, & a 'cool colors' side, where green & blue go... so when if you're looking in the chest for 'blue' you know right where to find it, instead of having to hunt thru all the shelves 2. the chest DOES NOT start with all the shelves for all the colors it could have, instead it has exactly as many shelves as it has currently stored colors. It's only huge when you put a million colors into it, when you have only 3 to 10, it's tiny. IRL, this property is actually exploited to use hashsets as a space efficient way to store sparse arrays.

[@PattyManatty]

@@kgoblin5084 actually the number of spots on the shelves before inserting any is implementation dependant. A "pure" hashmap has a memory location for every possible hash. Those aren't practical however, and most implementations will use "buckets". The set of all hashes get reduced down to buckets that they are a part of, and then that bucket is a regular list that needs to be iterated through if it has multiple items. As you get more items in the hash, at some point you need to increase the number of buckets in the chest. This is a very expensive rebalancing operation that requires basically rebuilding the entire hash table when you would like to make more space. If you know the number of elements the map will hold ahead of time you can allocate the necessary memory, but most of the time this is done dynamically and every now and then one of your hash inserts will take an oddly long amount of time

[@ablobofgarbage]

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

[@DJ_POOP_IT_OUT_FEAT_LIL_WiiWii]

As a programmer I don't get it though... computer are excellent at finding unique values in a data set. Even huge data sets and even the oldest mechanical computer did that very efficiently. I fail to see any scenario where you'd run out of computing resources for this class of problems. It is also an extremely simple problem. Maybe you can help me here, what is hard in counting unique elements? Why would you ever want to produce an inaccurate guess? I can only see this as interesting in the fields of statistics on infinite data sets which has little to do with programming.

[@ablobofgarbage]

​@@DJ_POOP_IT_OUT_FEAT_LIL_WiiWiithe video was about how counting unique elements is not an easy problem. If you use an array list or a linked list you will end up with O(n^2), using an ordered list would be O(n log n) (i think), and using a hashmap would be O(n) but use a lot of memory. HLL is O(n) but does not give an exact answer, but as the size of your data set increases the accuracy of HLL also increases. Companies like Google have unfathomable amounts of data, so for them this tradeoff is very much worth it.

[@aidenkt]

​@@DJ_POOP_IT_OUT_FEAT_LIL_WiiWii This mostly becomes a problem when a dataset starts ranging into the hundreds of thousands and millions. As fast as computers are at counting through one time, this would require a computer to run a script per number, per number. Say that it's for 4 numbers, it's not really that unreasonable to count 4 numbers individually since thats 10 checked numbers in total. However, scale that up to a few million: then we have an issue. This is especially the case for larger companies when these numbers need to be continually pulled-it's a massive waste of processing power. To give you an idea, say one comparison is 0.3 nanoseconds (the average amount of time it takes a computer to compare two numbers). This is SUPER fast. Let's say it's 100 numbers. Unfortunately, the time it takes for 100 is not 0.3 times 100. It is actually the 0.3 times 100! (factorial). That becomes as simple as a few milliseconds-that's still relatively fine. 0.0000028 But now take 10,000,000 numbers. The factorial of this is so high that most computers and calculators will refuse to even let you calculate the amount of commands you would have to do. This is the point where now, it's entirely unreasonable to finding unique values with the other method. Its reasons like this that you'll never see an exact amount of Google accounts in the world as it would far exceed this range. But of course, they still have to know a general amount right? That's where the solution presented in this video comes in.

[@BEN-ys6gu]

Well one use case was at the end, when you have a distributed data management system with multiple databases. Also, if the guess is really good, they might simply not need anything more accurate, so a resource-friendly algorithm is the best choice

[@ME0WMERE]

@@DJ_POOP_IT_OUT_FEAT_LIL_WiiWii The problem is, as he said, when there are trillions of items. A stack is O(n^2) cpu time so it's infeasible. A hash map needs at least the same order of magnitude of memory as there are unique items - and in this case, you have absolutely no idea how many unique items there are. Someone somewhere else in these comments mentioned using this method to estimate the size required for a hash map in order to count the exact number of unique items. That's a real-world use for this method.

[@macchicken98]

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!

[@thewhitefalcon8539]

Color shelf octarine with the cobwebs

[@vitulus_]

I would've preferred hashmaps to be explained as simply measuring some quality of the colour (hash) and then examining the stack corresponding to that quality. It avoids checking one massive stack, and instead much smaller stacks (buckets). Still simplified, but without losing any accuracy. Furthermore, a hashmap is technically a generalisation over the 'stack' approach, so one part of the video doesn't make sense to find a spot in-between too much space and one big stack given the hashmap literally can be adjusted for that!

[@CrittingOut]

Hashmap? No, magic chest.

[@tanvach]

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!

[@nothayley]

Can you share what you use it for? It's a brilliant algorithm, but I'm struggling to think of concrete use cases for it.

[@alternativeglasto]

@@nothayley I have also used this at work, I implemented it about eight (maybe?) years ago; I was working as a SQL compiler writer for a massively parallel database company, and called it "APPROXIMATE COUNT DISTINCT (var)" (I also implemented other APPROXIMATE aggregates using other techniques like this). As it was parallel we could do the work of doing the count of distinct values over multiple nodes, then merge the results, as this video alludes to. In my opinion that is the real point of hyper log log - being able to split the work over many nodes, then merge the results from all of them to get a final result that is close to the real answer.

[@cannaroe1213]

​@@alternativeglasto yeah throughout this I was like "oh neat, it's got cute cardinality fingerprint thing going on" and then when he said it was possible to aggregate these scores i had to pause the video and take a moment, that's wild! I mean it's not crazy, it's just sharing information about the used up "hash space" across a bunch of hashers working off the same map, but it's beautiful in it's simplicity. Counting the number of 0s is a single CPU instruction called finding the Least Significant Bit LSB. Putting something into the right bucket is as simple as bit shifting everything but the last N bits, that's the bucket ID. Concat these together and you have your distributable hash. Wild! It's a half-cryptographic, half-perceptual hash. I wish there was a wikipedia of algorithms, i'd love to buy all the programming books and compile such an encyclopedia.

[@tanvach]

@@nothayley we use it for product analytics via approx distinct count in SQL. The merge-ability allows distinct count to be run in parallel on a cluster. See Presto/Trino APPROX_SET. Actually we store the binary format in aggregated tables to allow fast set operations (not just counting unique users, but rolling time window unique users, churned users, etc). With small enough error setting it’s a worth while trade off. Consider that I process 10+ terabytes of data per query, and multiple petabytes of data for our org alone…

[@BEN-ys6gu]

​@@alternativeglasto did you use APPROXIMATE COUNT DISTINCT to count the number of years since you implemented it? 🗿

[@nsq2487]

Wished you had elaborated me on why exactly this algorithm is important, giving examples rather than just saying big tech companies use it

[@nitsanbh]

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!

[@cernejr]

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.

[@BreakingTaps]

It's both critical, but also trivial 🙂 I.e. you _must_ have a good pseudorandom hash function for this to work... but that's satisfied by any number of modern hash functions, which exist in easily obtained libraries for basically every language. So it ends up being a pretty moot point in practice. Grab a modern, fast hash function (murmurhash or similar) and use 64 or 128bit outputs and you're golden. I didn't want to derail the video talking about pseudorandom hash functions so just hand-waved it away :) Re: use-cases, it's used a lot in reporting, forensic investigations, analytics! Unique count of session IDs, IP addresses, src-dest tuples, etc etc. Typically it'll be used in a partitioned analytic scheme. Give me the count of unique session IDs over the last six months, partitioned by page on the website, country and language. That sort of thing.

[@cernejr]

@@BreakingTaps Thank you

[@Kerpeles]

I also started to wonder how this actually being used

[@albertrenshaw4252]

@@Kerpelesevery password is stored as the hash of the password. When you enter your password on a frontend, it hashes it locally and sends the hash back to the database, the database then compares the hashes of the password rather than the actual raw passwords. This is ideal because in the event of a hack only the hashes are released, not the raw passwords. Hashes are worthless because (not mentioned in the video) they are one way functions. Meaning you can get the hash value of an object easily but you can’t get the original object from a hash (for all intents and purposes, I already know some “ackshually” warrior is salivating with the knowledge of dictionary attacks)

[@einsteinx2]

@@albertrenshaw4252​​⁠​​⁠​​⁠ackshually he does mention it’s one way in the video at 4:46 “it’s a consistent, one-way transformation” ;)

[@WolfrostWasTaken]

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.

[@harmlesscreationsofthegree1248]

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!

[@phutureproof]

in your mind imagine putting the coins in a bag, and you ask the bag how many coins are in it, abstraction

[@harmlesscreationsofthegree1248]

@@phutureproof I tried that and it didn’t work. Good suggestion though

[@OtherWorldExplorers]

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

[@BreakingTaps]

Argh! Didn't even cross my mind, would have been perfect!

[@kylewhite5695]

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.

[@alexismandelias]

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.

[@miketout]

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.

[@SeaScoutDan]

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

[@puilp0502]

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

[@DarthMarioDM]

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

[@jonaslind9505]

Yeah I loved the discworld reference. Only thing missing is lots of little feet on the chest.

[@fractalgem]

There's a spider web on that part of the shelf, showing it never actually gets used :P

[@jsrodman]

Amusingly, I did bugfixing work on a product that implemented HyperLogLog. When it was added to the product and I was part of the technical review I asked "What is the boundary for inaccuracy which is expected for this implementation?" and the implementor had no answer. I said "How can we ever know if it is operating corrrectly if we hae no definition of what correct behavior is?" and the implementor had no answer. No one was happy that day.

[@dominikmuller4477]

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

[@Scyth3934]

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

[@christianbruneau777]

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

[@kasuha]

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.

[@BreakingTaps]

Yep, definitely! It excels in situations like counting unique session IDs, transaction IDs, IP addresses, Source-Desetination tuples, etc. Very high cardinality events that are likely stored in large (distributed) datasets across multiple servers. If the data fits on one machine, much better to just count it exactly 🙂

[@monkeytube9]

​@@BreakingTapsActually, it's useful for things like upvote tallying. Not for 10s of votes, but storing a few thousand user-ids for tons of topics/threads/comments takes more space than a sketch. And the HLL sketch de-duplicates votes very efficiently.

[@muskyoxes]

@@BreakingTaps It sounds like being distributed is everything. There isn't an overwhelming total count of anything you listed

[@gaboqv]

when objects you want to count are very complex this would save you from using 30 gbs of ram to using like 100mbs even if you aren't in the millions

[@kasuha]

@@gaboqv You can always count just their hashes. Statistical methods are only necessary when even the hashes can't fit in reasonable sized storage.

[@adarco99]

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!

[@steven_porter]

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

[@DethWench]

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.

[@areadenial2343]

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.

[@jamesedwards6173]

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

[@Amonimus]

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.

[@WarlordEnthusiast]

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

[@sethputnam5925]

Loved the Octarine reference hidden within the Magic Chest explanation.

[@videoharry_]

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

[@markzuckerbread1865]

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

[@BRUXXUS]

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.

[@AlmostM]

It is effectively "counting distinct values in a large set", and that could be any type of value. For example, you could count "how many different users have commented on this video".

[@davidmurphy563]

Ok, obviously you knew some of your audience would be programmers. I've paused at 4:39 to convey how much I chuckled at "it's a hash function". Chuckled in a nice way. Lovely, just lovely. Right, I'm hitting play. Great so far. Subbed.

[@davidmurphy563]

Ok, at the end of the vid. I could code that algorithm based on nothing but your explanation. Reply if you want me to, I'll post a video showing it working. Or don't, we all have better things to do. :) Anyway, very good video.

[@eldoprano]

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

[@dameanvil]

00:00 🎲 Understanding distinct elements in a large dataset is a crucial problem in computer science. 02:01 🗃 Traditional methods for counting distinct elements can be slow and memory-intensive. 03:02 🪄 Hyperlog log algorithm provides a faster and more memory-efficient solution. 03:56 📊 Hyperlog log leverages the concept of counting runs in binary sequences to estimate distinct elements. 06:48 🎰 It's a probabilistic algorithm, providing estimates rather than exact counts, but usually within 2% accuracy. 08:33 🖥 Hyperlog log allows merging results from separate computations, making it scalable across multiple computers. 11:53 📚 Interested viewers can explore more formal mathematics and simulations regarding the algorithm.

[@bj_]

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

[@Geitungur]

I imagine actual programmers were very sad when you called a list a 'stack'

[@morgan0]

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.

[@BreakingTaps]

It's not quite the same, but the scheme you are describing is very similar to an algorithm called CountMin (and a few related algos)! CountMin builds a frequency table in a probabilistic manner like HLL, so you can ask it "how many times have you seen xyz" and it will estimate a count for that item. It does this by hashing the element multiple times and using that to increment different counts in the datastructure.

[@morgan0]

@@BreakingTaps neat

[@AntonioNoack]

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

[@ozne_2358]

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

[@surenpetrosyan1603]

imagine you have a large amount of data and you have to find the number of unique items among those. HyperLogLog is an efficient counting algorithm. you could use it in an airport company to find from what countries your tourists come from, taking out the “duplicates” from the same country.

[@TumbleFig]

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.

[@danielsmullen3223]

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

[@HAMYLABS]

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.

[@DJ_POOP_IT_OUT_FEAT_LIL_WiiWii]

I fail to see practical use. In real world scenario a hash table gives excellent performance on huge data-set no problem. Video creator has mentioned in comments it's useful when data is distributed on different machines and can't be transferred all in one place. Makes sense but then the problem of counting unique element is not hard and inefficient as the video claims. The real problem is just that they can't get all data in the same process to check uniqueness.

[@alterego3734]

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

[@alterego3734]

And then there's Bloom filters too.

[@alterego3734]

Of course, they use exponentially more space than HLL, since they not only (approximately) count seen colors, but also keep track of which colors have been seen. So that is the real advantage of HLL.

[@BreakingTaps]

It's a reasonable consideration when dealing with very large datasets. If you want decent performance you need a modest load factor, and it all becomes problematic when you have to transfer all the maps to a central location for merging. But I was trying to keep the topics simple for non-programmers, so grain of salt to the explanation in the video :) Bloom and cuckoo filters are indeed cool. But they can saturate far more easily than HLL and give false positives, so have their own considerations like HLL.

[@Ryan_Thompson]

​ @BreakingTaps Sure, but the problem with your description of hashes was that you said (and showed) that "physics is still physics. It needs a huge amount of storage for every *potential* color, even if we didn't actually see those colors in our pile". That's not at all how hashes work! Hashes have an O(n) worst case storage efficiency, where n is the number of elements you have inserted into the hash. In this case, you'd be inserting elements like Red→1, so n would be the number of *unique* elements *you have seen,* (not all *potential* elements, as you stated) as finding another red block would simply increment Red→2 without requiring more storage (and that's (exactly!) an O(1) operation, too). Now, don't get me wrong, HLL is asymptotically *way* better, a good fit for the datasets you described, and is a very cool algorithm, but as an old Perl programmer from *way* back, I love my hashes, and don't like to see them getting an undeserved bad rap.😜

[@BreakingTaps]

Haha well, I wasn't trying to disparage hashmaps! They are great. 🙂 But trying to convey loading factor to a lay audience is not an easy task (or really relevant tbh) so I just sidestepped it. Trying to discuss how it's not actually empty shelving but multi-purpose slots that multiple colors can use, but only one at a time, so have complicated collision-resolution mechanism and the shelves then resize when they get too full... way too complicated for something that's not the video's main topic. I wanted folks to understand that maps trade space for performance and I think the analogy of long, empty rows of shelving is fine for that. And to be honest even a load factor of say 0.7 ends up being pretty expensive when working on enormous datasets. Re-allocating the map's memory multiple times as the cardinality grows is a non-negligible expense. If you don't wan to pay that runtime cost you end up in a situation very much like the empty shelves: you over-allocate a large block of memory and it sits idle if you accidentally have a lower-cardinality scenario. If you're potentially in a situation where HLL makes sense -- millions to billions of distinct elements -- that's a very serious cost, and exacerbated by the merge-cost at a reduction node.

[@ViralKiller]

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

[@rammsund]

So cool! More videoes like this please 😊

[@alex.g7317]

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

[@huzzzzzzahh]

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.

[@BreakingTaps]

Oh no, I totally didn't think about that! Oof😢 Pretty big oversight on my part, should have picked something like shapes instead of colors. I'll keep that in mind for future videos, thanks for bringing it up!

[@huzzzzzzahh]

@@BreakingTaps it happens! It’s so incredibly easy to take what we have for granted. There’s some good accessibility guides around too that make it a lot easier; for example there are some text/background combinations that I would never have imagined could be a problem, yet are for some people.

[@leolen8029]

@@BreakingTapsDon't worry, i'm colorblind and I still really enjoyed the video! The graphics were really incredible!

[@GiddyThis]

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

[@goat9199]

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

[@BreakingTaps]

Condolences! 😢

[@_abdul]

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 ❤

[@aroundandround]

Frankly, to a computer scientist, this explanation was not easy to understand at all. It would have been easier if you explained it without dumbing it down.

[@paulblart7378]

He mentions in the beginning that he made this for a general audience to understand, not just computer scientists. Also, it wasn't any harder to understand lol. You're not special

[@getuliomartins5005]

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!

[@Robert_McGarry_Poems]

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.

[@Alexander_Sannikov]

this approach reminds me of proof of work: the only way to find a value that has a hash with n zeroes at the end is to try 2^n values on average. so if you can present me a value that has a hash with n zeroes at the end, it means you have calculated about 2^n hashes to find it. which is the basis of how crypto currency works.

[@elisgrahn6768]

Fantastic video! Loving the animations and sound effects. 😄

[@nWestie]

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

[@lamphobic]

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.

[@Kreliho]

Excellent video and animation! You've outdone yourself.

[@darkmann12]

"glossed over some details" bruuu i was already lost 😫😫

[@alipony]

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

[@TheLoneWolfling]

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

[@drdca8263]

Does the HMAC with a key differ from "add a (fixed, secret) salt before taking the hashes" ? (would it be less secure, provided that a cryptographic hash function is used?)

[@TheLoneWolfling]

​@@drdca8263 Look up length extension attacks. To oversimplify, an HMAC is "just a hash with salt, but actually secure this time". (As a side note: if it has to be secret, it's not a salt. It's a key. Salts retain their usefulness even if the value is public; keys do not.)

[@robinspanier7017]

2:37 nice touch that teal is in perfect condition for the not so common colors, because its currently everyhwere

[@NoblePineapples]

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.

[@tanchienhao]

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

[@lonely_space_egg]

I love the animation style here, reminds me of old edutainment games like Humongous Entertainment. Perfect fit for the video!

[@perlguiman]

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

[@MrApple-yw9vp]

Wow your narration goes so well with animation. Feels like I watched at TedEd

[@solnijko]

3:15 sounds like a great deal

[@Ayor88]

i don't know why yuoutube recommand me this video so many times, but I'm glad I watched it !

[@transationalien]

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

[@ianalvord3903]

So to mess this up, all I have to do is know which color has the most zeros and just include it?

[@elEd0]

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.

[@capsey_]

I went from "hmmm that seems like quite a rough estimate" to "wow you can change the accuracy that's a neat trick" to "OMG YOU CAN PARALLELIZE IT THAT'S GENIUS"

[@Flopsaurus]

It's incredible this is your first animated video.

[@robinhodson9890]

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.

[@DJ_POOP_IT_OUT_FEAT_LIL_WiiWii]

it's obvious that real world computing systems do count unique element very efficiently and very accurately with a variety of algorithms. mainframes do it all the time, they could do it in the 1950s.. As video creator stated in a comment, the real issue is when data is distributed across different network and you can't transfer all data in one place to perform the computation. I'm at a complete loss to understand why one would use this inaccurate algorithm outside distributed data hosting scenarios. Even Facebook would benefit from more accurate metrics. The government certainly count unique attributes in all their databases accurately, no reason social networks wouldn't. The processing cost is really not that high too.

[@joshuajoab9313]

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!

[@jonathandawson3091]

"you don't need to know anything about programming to understand how it works" that statement would usually make me click away lol, but your video was refreshing and not dumb! i think you're gifted like Feynman, very few people are.

[@sharpfang]

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.

[@M0nu5]

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

[@ninocraft1]

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

[@clementboutaric3952]

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 !

[@YeloPartyHat]

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

[@ShaneGadsby]

Fantastic video, especially loved the Discworld references @2:32, with Octarine and The Luggage!

[@chriku]

GNU Terry Pratchett

[@deathfxu]

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

[@Sylfa]

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.

[@cubandarknez]

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.

[@NatiiixLP]

It's a bit misleading to say that HashMaps are large, but it's even more confusing to completely skip over how this magical merging of distributed algorithms works, although I'm aware that both of those issues are addressed in the pinned comment. I was also confused as to how the error could just 2% if we're talking in terms of powers of two, but of course, that makes sense with the follow-up explanation of using multiple different buckets.

[@smellsofbikes]

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

[@cfehunter]

I was about to complain about this being overly dependent on the hashing algorithm used, but you covered that by saying that every bit has to have a 50:50 chance of 0 or 1. Though I feel like this falls over for data sets with small variation. If you only have a handful of items in a set then you've got a fairly reasonable chance of it being off by a few orders of magnitude.

[@GrilledCheeseSandwich1]

Hashmaps don't need to reserve space. You start with a size of 16 and double it every time you reach 70% capacity. The cost of doubling does not push the average time to add higher than O(1)

[@Jimunu]

Been here since your epoxy lens and maybe before. Remember the first time I noticed you tried a more creative way to present your work. I appreciate it.

[@BreakingTaps]

🥰🥰🥰

[@mskiptr]

Whaa!? Why does this awesome explanation only have like 9k views? On a different note, after the introduction I was kinda expecting the trick to be in not actually looking at the whole dataset. As in, you browse it randomly and observe how often you discover new elements. When that gets rare you guess how many more there are (and also what's the count of each)

[@BreakingTaps]

Oh goodness, that brings up a whole field of techniques that I absolutely love: sub-sampling! Will add it to my potential todo list in the future. You're absolutely correct, this technique touches all the data once. Which is a big win compared to traditional techniques... but still very expensive if `n` is very large. Sub-sampling, stratified sampling, etc are all sub-linear because they don't even bother looking at all the data. Really interesting field with some powerful capabilities (and big caveats).

[@mskiptr]

@@BreakingTaps I guess the _log log_ in the name made me expect something like O(n ↦ log(log(n))) time complexity

[@monkeytube9]

I ended up implementing HLL++ for work at an online ad company. Add a bit of KMV and Jaccard similarity, and you can slice and dice demographics for hundreds of millions of users in a flash.

[@BreakingTaps]

Nice! It's such a nice, compact algo to implement but so powerful!

[@vheyney]

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

[@tylerpeterson4726]

I knew there had to be some way of preventing a single lucky item with many trailing zeros from throwing off the count, but I didnt expect the solution to be so simple and compact

[@DJ_POOP_IT_OUT_FEAT_LIL_WiiWii]

but the solution doesn't prevent two lucky items from throwing off the count, you're just piling more compute work to reduce inaccuracies of a totally unreliable algorithm, you really need to count the unique items if you want anything this is trustable. and it's such a simple problem to count unique elements you'll almost never have trouble doing that. that it has an average error margin of 2% means nothing in regards to accuracy. can you afford to have 100% inaccurate result 1% of the time in any kind of practical computing application? doesn't happen often and there's really no performance to be gained on any real world scale system