Estimate item frequency with bounded memory#
A query stream contains too many distinct terms for an exact counter per term. Count-Min Sketch updates several hashed counters and estimates an item's frequency from them. Hash collisions can make the estimate too high rather than exact.
It can support trending-query candidates or heavy-hitter detection when follow-up verification is possible. It should not replace an exact ledger, quota, or inventory count.
| Structure | Question |
|---|---|
| Bloom filter | Have I probably seen this item? |
| HyperLogLog | Approximately how many distinct items exist? |
| Count-Min Sketch | Approximately how often has this item appeared? |
Related practice problems
Use the manifest-backed prompts below to apply this lesson in a complete design.
- Probabilistic data typesRedis Documentation
Reach this point to mark the lesson as read.