Hey I wrote the article —- the way I think of HyperLogLog and similar (but different) approaches like bloomfilters and count-min sketches is that the key insigh

Hey I wrote the article —- the way I think of HyperLogLog and similar (but different) approaches like bloomfilters and count-min sketches is that the key insight is hashing. The fact that we can reduce some piece of data to a hash, then work on the distributions of data/entropy of those hashes in number space many different ways is what makes these data structures work. I think of it this way —- if you have a hashing algo that turns “someone@example.com” into “7395718184927”, you can really easily count with relative certainty how often you see that email address by keeping a sparse numeric associative array. Getting the same exact value again produces the same hash. Obviously doing this isn’t SUPER useful because then you just get strict cardinality amount (same as just checking equality with the other keys). but if you choose a weak enough, fast hashing function (or multiple, in the case of a count-min sketch), you can have collisions in what some values hash to but others do not — so that means there will be some amount of error — you can control that to suit your needs, on a scale of everything in one bucket to exact cardinality # of buckets. Here’s an actual proper guide (CS lectures, as you might expect!) I found after a quick search, which you might find useful: https://williams-cs.github.io/cs358-f21/lectures/lecture10/lecnotes-streaming.pdf https://williams-cs.github.io/cs358-f21/lectures/lecture10/l... (IMO focus on the algorithm description) And here’s some old HN discussion: https://news.ycombinator.com/item?id=7508658 https://news.ycombinator.com/item?id=7508658 To really try and understand the concept I found it useful a while back to actually try and build it: https://vadosware.io/post/countmin-sketch-in-haskell/ https://vadosware.io/post/countmin-sketch-in-haskell/ http://dimacs.rutgers.edu/~graham/pubs/papers/cmencyc.pdf http://dimacs.rutgers.edu/~graham/pubs/papers/cmencyc.pdf (This paper has a really good visual depiction) I find the count-min sketch to be much more approachable