Top-K Trending

Top-K asks a deceptively simple question: what are the K most popular items right now? — trending hashtags, top search queries, most-viewed products in the last hour. The twist is scale: events arrive as a firehose (millions/sec) and you can't afford to keep an exact count for every distinct item, nor re-sort everything on every query. The art is getting an approximately correct answer cheaply, leaning on Data Structures for Big Data.

1. Requirements

Functional:

• Ingest a stream of events (each names an item: a hashtag, query, product).
• Return the top K most frequent items over a recent window (e.g. last hour).

Non-functional:

• Firehose ingest — millions of events/sec.
• Fast reads — top-K served instantly, precomputed.
• Huge cardinality — billions of distinct items; can't store a counter per item.
• Approximate is acceptable — the #1 trending tag being off by a few counts doesn't matter; the set of top items should be right.

2. Why the naive approach fails

"Keep a hashmap of item→count, sort, take top K" works on one machine for small data and breaks at scale:

• Memory: billions of distinct items won't fit in a map.
• Sorting: re-sorting on every query is O(n log n) over a huge n.
• Distribution: the stream is spread across many ingest nodes — no single map sees everything.

So we approximate the counts and maintain the top-K incrementally.

3. The building blocks

Count-Min Sketch — a fixed-size probabilistic counter. It estimates any item's frequency in constant memory regardless of how many distinct items exist, by hashing each item into several small counter arrays and taking the min on read. It can slightly over-count (never under), which is fine here. This solves the "can't keep a counter per item" problem (Big Data Structures).

A heap of size K — maintain a min-heap of the current top K. For each event, update the sketch, read the item's estimated count, and if it beats the heap's minimum, insert it. The heap gives you the answer in O(1) to read and O(log K) to update.

event → Count-Min Sketch (estimate count) → compare to top-K heap → maybe update heap
query → read the heap (already the answer)

4. The sliding window

"Trending now" means recent, so counts must decay — a tag hot yesterday shouldn't dominate today. Approaches:

• Bucketed windows: keep a sketch per small time bucket (e.g. per minute) and sum the last N buckets for "last hour," dropping the oldest bucket as time advances. Simple and exact-ish at the window boundary.
• Exponential decay: continuously age counts so recent events weigh more. Smoother, less bookkeeping.

5. Distributing it

The firehose is spread across many ingest nodes, so compute top-K in two layers (map-reduce in spirit):

each ingest node → local sketch + local top-K (over its slice of the stream)
aggregator       → merge the local sketches / local top-Ks → global top-K

Count-Min sketches merge by summing their arrays, which makes this clean: each node sends its compact sketch and local top candidates periodically; the aggregator combines them into the global answer. A stream processor like Flink is purpose-built for exactly this windowed aggregation.

6. Serving

The global top-K is small — cache it in Redis (even a sorted set) and refresh it every few seconds. Reads are then a single trivial lookup, fully decoupled from the ingest firehose.

Deep dives

• Exact top-K: if you truly need exact counts (billing, not trending), you can't approximate — you aggregate precisely in a stream processor and accept the higher cost, like the Ad Click Aggregator.
• Hot-key skew: a viral item hammers one hash bucket/partition — mitigate with local pre-aggregation before the merge.
• Multiple windows: serve 1h / 24h / 7d by keeping buckets at multiple granularities.

What to emphasise

Name the approximation and the two-layer aggregation:

"At firehose scale I can't keep an exact counter per item, so I'd estimate frequencies with a Count-Min Sketch — constant memory, slight over-count, which is fine for trending — and maintain a size-K min-heap for the current leaders. 'Now' means a sliding window, so I bucket counts per minute and sum the recent buckets, dropping old ones. The stream is distributed, so each node keeps a local sketch and top-K and an aggregator merges them — sketches merge by summing — giving a global top-K that I cache in Redis for instant reads. I'd run the windowed aggregation in a stream processor like Flink."

Next up: Ride Sharing — matching riders to nearby drivers in real time.