A problem so hard even Google relies on Random Chance

Подписаться 423 тыс.

Просмотров 1,2 млн

50% 1

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

Наука

Опубликовано:

27 июн 2023

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 1,2 тыс.

@BreakingTaps 11 месяцев назад

🚨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 11 месяцев назад

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

@iwersonsch5131 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@@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 11 месяцев назад

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

@bjarnivalur6330 11 месяцев назад

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_ 11 месяцев назад

This is the core essence of it.

@XerosOfficial 11 месяцев назад

@_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 11 месяцев назад

@_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 11 месяцев назад

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 11 месяцев назад

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.

@pafnutiytheartist 11 месяцев назад

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

@phizc 11 месяцев назад

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 11 месяцев назад

@@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 11 месяцев назад

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

@kgoblin5084 11 месяцев назад

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 11 месяцев назад

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

@BreakingTaps 11 месяцев назад

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 11 месяцев назад

Nope! I'm just fine with it

@Yenrabbit 11 месяцев назад

Really great, thanks for sharing!

@vegasu9418 11 месяцев назад

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

@Dinnye01 11 месяцев назад

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

@MrBeaach 11 месяцев назад

consider entering this video into the SoME3 competition,

@decb.7959 11 месяцев назад

- 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 11 месяцев назад

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 11 месяцев назад

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

@cheesebusiness 11 месяцев назад

“asynchronously” Probably you meant “in parallel”

@sausas8209 11 месяцев назад

@@cheesebusiness tHreAdEd

@mrbrianakias1 11 месяцев назад

@@cheesebusinessit's a programming term

@ablobofgarbage 11 месяцев назад

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 10 месяцев назад

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 10 месяцев назад

@@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 10 месяцев назад

@@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 10 месяцев назад

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 7 месяцев назад

@@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 11 месяцев назад

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 11 месяцев назад

Color shelf octarine with the cobwebs

@vitulus_ 11 месяцев назад

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 11 месяцев назад

Hashmap? No, magic chest.

@nitsanbh 11 месяцев назад

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!

@tanvach 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@@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 11 месяцев назад

@@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 10 месяцев назад

@@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 10 месяцев назад

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

@OtherWorldExplorers 11 месяцев назад

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

@BreakingTaps 11 месяцев назад

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

@cernejr 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@@BreakingTaps Thank you

@Kerpeles 11 месяцев назад

I also started to wonder how this actually being used

@albertrenshaw4252 11 месяцев назад

@@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 11 месяцев назад

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

@alexismandelias 11 месяцев назад

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 11 месяцев назад

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.

@steven_porter 11 месяцев назад

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

@WolfrostWasTaken 10 месяцев назад

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.

@SeaScoutDan 10 месяцев назад

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

@Scyth3934 11 месяцев назад

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

@areadenial2343 11 месяцев назад

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.

@GiddyThis 11 месяцев назад

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

@adarco99 11 месяцев назад

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!

@DarthMarioDM 11 месяцев назад

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 11 месяцев назад

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

$@fractalgem$

@fractalgem 11 месяцев назад

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

@WarlordEnthusiast 11 месяцев назад

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

@kylewhite5695 11 месяцев назад

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.

@dominikmuller4477 6 месяцев назад

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

@harmlesscreationsofthegree1248 11 месяцев назад

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 11 месяцев назад

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

@harmlesscreationsofthegree1248 11 месяцев назад

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

@puilp0502 11 месяцев назад

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

@alex.g7317 11 месяцев назад

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

@perlguiman 11 месяцев назад

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

@videoharry_ 11 месяцев назад

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

@jamesedwards6173 10 месяцев назад

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

@markzuckerbread1865 11 месяцев назад

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

@DethWench 9 месяцев назад

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.

@eldoprano 11 месяцев назад

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

@bj_ 11 месяцев назад

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

@getuliomartins5005 11 месяцев назад

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!

@YeloPartyHat 11 месяцев назад

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

@danielsmullen3223 11 месяцев назад

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

@christianbruneau777 5 месяцев назад

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

@elisgrahn6768 11 месяцев назад

Fantastic video! Loving the animations and sound effects. 😄

@kasuha 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@@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 11 месяцев назад

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

@gaboqv 11 месяцев назад

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 11 месяцев назад

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

@BRUXXUS 11 месяцев назад

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 11 месяцев назад

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

@NoblePineapples 11 месяцев назад

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.

@_abdul 11 месяцев назад

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 ❤

@morgan0 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@@BreakingTaps neat

@ozne_2358 11 месяцев назад

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

@surenpetrosyan1603 11 месяцев назад

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.

@alipony 11 месяцев назад

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

@joshuajoab9313 11 месяцев назад

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!

@rammsund 11 месяцев назад

So cool! More videoes like this please 😊

@alterego3734 11 месяцев назад

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

@alterego3734 11 месяцев назад

And then there's Bloom filters too.

@alterego3734 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@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 11 месяцев назад

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.

@nWestie 11 месяцев назад

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

@M0nu5 11 месяцев назад

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

@huzzzzzzahh 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@@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 6 месяцев назад

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

@goat9199 11 месяцев назад

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

@BreakingTaps 11 месяцев назад

Condolences! 😢

@jsrodman 10 месяцев назад

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.

@Giorgosdnv 11 месяцев назад

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

@smellsofbikes 11 месяцев назад

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

@nsq2487 10 месяцев назад

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

@sethputnam5925 11 месяцев назад

Loved the Octarine reference hidden within the Magic Chest explanation.

@st3althyone 11 месяцев назад

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

@lamphobic 9 месяцев назад

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.

@greenboy256 11 месяцев назад

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!

@bill_the_duck 11 месяцев назад

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.

@Kreliho 11 месяцев назад

Excellent video and animation! You've outdone yourself.

@Amonimus 11 месяцев назад

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.

@arcrad 11 месяцев назад

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

@phillustrator 10 месяцев назад

Some mad After effects skills here. Amazing work.

@summer_rains 11 месяцев назад

Love your style of explaining and the animations!

@user-vr3ex1fj7c 11 месяцев назад

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

@foobars3816 11 месяцев назад

This was amazing. Subscribed!

@danbromberg 11 месяцев назад

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

@SamGalbraith 7 месяцев назад

Very clearly and intuitively communicated and the cartoon visualisation really helped 👏

@jlhudson4521 11 месяцев назад

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

@joshroolf1966 11 месяцев назад

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

@vheyney 11 месяцев назад

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

@Kadmao 11 месяцев назад

You did a really good job explaining

@cmatrix6720 11 месяцев назад

This was amazing. Please do more :))

@AntonioNoack 11 месяцев назад

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

@toilettime8765 11 месяцев назад

Awesome animation and production value.

@JordanCrawfordSF 11 месяцев назад

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

@basedifear 11 месяцев назад

Incredibly well explained video. Well done.

@hoodiegal 10 месяцев назад

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

@3thanguy7 11 месяцев назад

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

@clementboutaric3952 11 месяцев назад

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 !

@herzogsbuick 11 месяцев назад

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

@tanchienhao 11 месяцев назад

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

@TheLoneWolfling 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

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

@bogokellmeyer3693 11 месяцев назад

Such a cool, simple explanation! Loved it

@sharpfang 11 месяцев назад

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.

@cubandarknez 11 месяцев назад

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.

@HAMYLABS 11 месяцев назад

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 10 месяцев назад

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.

@bottlekruiser 11 месяцев назад

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

@TotesCray 11 месяцев назад

Interesting topic and great animation! Love this channel.

@deathfxu 11 месяцев назад

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

@Robert_McGarry_Poems 10 месяцев назад

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.

@gwenrees7594 10 месяцев назад

Thank you, I don't know anything about algorithms but I enjoyed this and learned something new :)

@sillydilly2725 11 месяцев назад

Great visualizations! Good work on this video

@haraseesgill8491 11 месяцев назад

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.