A problem so hard even Google relies on Random Chance
Вставка
- Опубліковано 27 чер 2023
- Head to brilliant.org/BreakingTaps/ to get a 30-day free trial. The first 200 people will get 20% off their annual subscription.
Watch this video ad free on Nebula: nebula.tv/videos/breakingtaps...
-------------------------------------------------------
Today we're looking at HyperLogLog, an algorithm that leverages random chance to count the number of distinct items are in a dataset. It does this by tracking the longest run of zeros in a binary sequence, and uses that as an estimate of cardinality.
HLL is a probabilistic algorithm, meaning it's a guess rather than true answer. But due to some clever tricks it is usually within 2% of the correct value, and can do it both quickly and in a memory-efficient manner. A 512kb datastructure can accurately process trillions of items and terrabytes of data, which is pretty impressive!
When I made this video, I didn't realize that another #SoME3 was in progress. But a bunch of viewers suggested I enter the video, so I guess this is will be part of the event!
----------------------
🔬Patreon if that's your jam: / breakingtaps
📢Twitter: / breakingtaps
📷Instagram: / breakingtaps
💻Discord: / discord
----------------------
Journal papers:
Flajolet, Philippe, et al. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." _Discrete Mathematics and Theoretical Computer Science_. Discrete Mathematics and Theoretical Computer Science, 2007. algo.inria.fr/flajolet/Public...
Heule, Stefan, Marc Nunkesser, and Alexander Hall. "Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm." _Proceedings of the 16th International Conference on Extending Database Technology_. 2013. static.googleusercontent.com/...
Earlier work:
Durand, Marianne, and Philippe Flajolet. "Loglog counting of large cardinalities." _Algorithms-ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings 11_. Springer Berlin Heidelberg, 2003.
Flajolet, Philippe, and G. Nigel Martin. "Probabilistic counting algorithms for data base applications." Journal of computer and system sciences 31.2 (1985): 182-209.
Articles:
- towardsdatascience.com/hyperl...
- engineering. 2018/12/13... - Наука та технологія
🚨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.
Quite amazing thing. Super helpful to keep in mind for the future!!!
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
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?_
@@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.
@@iwersonsch5131 first thing I thought of.... The set grows (and gets slower) but should make for an accurate answer?
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
This is the core essence of it.
It also doesn't solve the original problem at all, it will ~always be totally wrong about the actual number that the stack/hashset would actually solve.
@@_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.
@@_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.
@@KatherynneF and @XerosOfficial , You are both right. Like I said, it solves a totally different problem than the original problem of knowing how many unique items there are. Instead it solves for a probabilistic approximation that can be used for other purposes than when you need to know the actual count. They aren't equivalent, as you can't switch one method for the other in any system.
To be more clear, the original solutions resolved the exact count and a set (HashSet/Array) of all the unique data. While this algorithm didn't return any of those.
Explaining hash tables as "magic chests" is very cute but surprisingly accurate.
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.
@@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.
As described it's more of a hash set than a hash map/table.
But of course the fundamentals are the same
@@phizc*Laughs in std::unordered_multiset*
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.
- 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 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. 😊
@@ColinTimmins ChatGPT makes things up because it's just a fancy regression model. Please do not use it for data analysis.
“asynchronously”
Probably you meant “in parallel”
@@cheesebusiness tHreAdEd
@@cheesebusinessit's a programming term
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 🙂
Nope! I'm just fine with it
Really great, thanks for sharing!
nice vid! ever going to try to beat Sam Zeloof at higher res transistor fabrication?
It's perfectly fine. I'll consume your content no matter what.
consider entering this video into the SoME3 competition,
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!
Color shelf octarine with the cobwebs
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!
Hashmap? No, magic chest.
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
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.
@@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.
@@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.
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
@@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.
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.
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.
@@BreakingTaps Thank you
I also started to wonder how this actually being used
@@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)
@@albertrenshaw4252ackshually he does mention it’s one way in the video at 4:46 “it’s a consistent, one-way transformation” ;)
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!
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!
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.
@@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.
@@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.
@@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…
@@tanvach that really doesn't sounds like something you use all the time. what I do use all the time is hash tables to count unique elements...
Missed opportunity.
One of the cubes should have been a Portal companion cube.
Argh! Didn't even cross my mind, would have been perfect!
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.
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.
I like the format! Very different from your usual work, but it felt nicely polished and worked well with the topic.
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.
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!
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.
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 :)
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.
Please make more of these! I like this format and you have always been an exciting teacher!
2:32 Octarine. I approve of this reference. 🙂 (And 42 shortly after. lol)
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. ❤
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!
hi! Interesting to see an animation-only video from you, but you did a great job on it!
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!
in your mind imagine putting the coins in a bag, and you ask the bag how many coins are in it, abstraction
@@phutureproof I tried that and it didn’t work. Good suggestion though
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 ^^
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'm glad I saw a short of yours so I could come back and watch everything I've missed.
This guy leans so hard into the "programming-as-wizardry" metaphor that his cubes can be the color of magic. Pratchett would be proud.
Yeah I loved the discworld reference. Only thing missing is lots of little feet on the chest.
There's a spider web on that part of the shelf, showing it never actually gets used :P
I just understood HLL in less than 10 minutes, a concept I struggled to understand for more than 2 years. Your explanation is phenomenal!
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 ❤
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
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.
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 🙂
@@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.
@@BreakingTaps It sounds like being distributed is everything. There isn't an overwhelming total count of anything you listed
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
@@gaboqv You can always count just their hashes. Statistical methods are only necessary when even the hashes can't fit in reasonable sized storage.
This was a great video and you did a fine job of explaining the concepts behind HLL in simple terms.
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 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!
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.
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".
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.
This is so well explained! Even for me as a programmer it is better to hear about it in a easier way.
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.
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.
@@BreakingTaps neat
6 years of watching math UA-cam 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 :)
I love your channel and the videos you make. It's always a highlight to see new videos appearing.
2:46 That is _not_ the problem with hash maps. They can actually be quite space-efficient.
And then there's Bloom filters too.
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.
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.
@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.😜
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.
So cool! More videoes like this please 😊
Love how you took time to animate all of this! Gives a unique style to your videos
Love the animation style! Im glad i clicked on this video. You did a great job of breaking down and explaining this topic
Interesting video but I would have liked to see a bit more on how this algorithm is used on in practice.
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.
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.
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!
@@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.
@@BreakingTapsDon't worry, i'm colorblind and I still really enjoyed the video! The graphics were really incredible!
The content is great and really interesting, but I love your graphics design on this as well. This is really nicely explained, graphically.
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!
Damn, was just about to click away, but then you told me not to. Now I'm a sub. 😢
Condolences! 😢
I LOVE THIS VIDEO!! Killer work, thank you so so much!
Super interesting vid bud, keep up with the good work. Waiting for more algorithm videos in the future ;)
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.
This is a fantastic and highly engaging, interesting video. Keep up the awesome work, look forward to seeing more like this.
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.
It was a nice change of pace, thanks for the snazzy explanation.
Loved the format and animation. Very cool subject. Happy to learn about it!
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.
Loved the Octarine reference hidden within the Magic Chest explanation.
Fantastic video! Loving the animations and sound effects. 😄
This was a wonderful topic, graphics, and presentation...thanks!
Love your style of explaining and the animations!
This was amazing. Subscribed!
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 :)
Excellent video and animation! You've outdone yourself.
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
an unexpected style and topic from your channel
i love it, do more!
Incredibly well explained video. Well done.
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 loved the way you explained such a hard thing with a very understandable way
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!
Wow so glad you made a video for SoME3!! Unexpected given your other videos but pleasantly surprised! Nice video :)
You did a really good job explaining
Interesting topic and great animation!
Love this channel.
I love the animation, as a software engineer - it's sooo on point well done!
That was a very clear presentation and your animations are great!
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.
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
Some mad After effects skills here. Amazing work.
This is some gold level content right here.Appreciate it❤❤
Very clearly and intuitively communicated and the cartoon visualisation really helped 👏
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 ;)
Such a cool, simple explanation! Loved it
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.)
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?)
@@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.)
very good explanation of a very interesting algorithm. great visual aids to help understanding. well done!
Thank you, I don't know anything about algorithms but I enjoyed this and learned something new :)
Great visualizations! Good work on this video
This was amazing. Please do more :))
This is awesome content!
Keep it up!
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.
Really cool video with well explained content! Thank you!
You're right, this video is different -- but it's fabulous. Well done!
Oh neat! I've used this via Apache Druid which implements the Apache Datasketches implementation of this.
Thank you for the explanation!
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 !
more of this style of concept explanation please!
Wow your narration goes so well with animation. Feels like I watched at TedEd
really simple and easy explanation
Awesome video! You should make one on Bloom Filters next. Those also blew my mind when I first learned about them.
Oh yeah, same here! Bloom and Cuckoo filters are definitely in my top tier list of favorite algos. Will keep it on the short list!