Individual probabilistic structures become most powerful when combined to solve problems that neither could solve alone. The Top-K frequency problem — "what are the 10 most popular items right now?" — is a canonical example.
The Problem
You are building a "Trending Products" widget for an e-commerce site. You want to show the top 10 products viewed in the last hour. You have 10 million distinct products and only 10 MB of RAM for this feature. Exact counts are not required — it is acceptable if the 11th most popular product occasionally appears instead of the 10th.
The Solution: Count-Min Sketch + Min-Heap
Count-Min Sketch (CMS): Tracks the estimated frequency of every product view. A CMS with w=2000, d=7 uses about 224 KB — well within budget — and can handle billions of events with bounded error.
Min-Heap of size 10: Tracks the current Top-10 candidates. A min-heap keeps the smallest element at the root, making it efficient to check whether a new candidate deserves to displace the current minimum.
The algorithm:
On each product view event for product_id P:
1. cms.increment(P)
2. estimated_count = cms.query(P)
3. if P is already in the heap:
update P's count in the heap, re-heapify
4. else if heap.size() < 10:
heap.insert(P, estimated_count)
5. else if estimated_count > heap.minimum_count():
heap.remove_minimum()
heap.insert(P, estimated_count)
Why this works: The CMS provides a fast, memory-efficient frequency estimate for any product. The min-heap maintains the top candidates without scanning all 10 million products. The combination answers "what are the top 10?" in O(log 10) = O(1) time per event, using under 1 MB of RAM.
The error mode: Because CMS overestimates frequencies (never underestimates), a product might enter the top-10 heap slightly earlier than it should. It will not cause a truly unpopular product to appear in the top-10 — only products with genuinely high view counts will accumulate enough CMS increments to compete. The error is bounded and predictable.
This pattern generalizes to any Top-K problem: replace the CMS with any frequency estimator, and replace the min-heap size with K. It is used in network traffic analysis (top talkers), log analytics (most frequent error codes), and recommendation systems (trending content).