A Count-Min Sketch is a data structure that estimates how often something appears in a large dataset while using very little memory. It relies on a table and hash functions to map items to specific spots in the table. Adding an item increases the values in those spots, and checking an item’s count returns the smallest value from them. While not exact due to possible collisions, it’s efficient and great for approximate counts when precision isn’t critical.

In this talk, we’ll explore:
• What this data structure is
• How it works internally
• How I used it to build an efficient version of Trending Topics for Bluesky

By the end of this session, you’ll have a clear understanding of Count-Min Sketches, why they’re valuable for handling large-scale data efficiently, and how you can apply them to solve real-world problems.

https://speakerdeck.com/raphaeldelio/count-min-sketch-an-efficient-probabilistic-data-structure