Trending Topics System Design: Count-Min Sketch, Top-K and Time Decay

Exact counting breaks in three ways at once. Memory grows with every new tag, the biggest tags are always the same old ones, and one spammer can push any tag to the top.

Picture a common setup. A social app in India gets about 2 crore (20 million) posts an hour during a cricket final. It wants a "Trending in Mumbai" box that refreshes every minute. The setup is made up, but the problems are the ones every trends system meets.

This guide is about trending topics system design for that app. The first try is a hash map from tag to count, updated on every post. It works on a laptop. In production it fails like this:

• Most tags appear once or twice and are never seen again, yet each one takes a slot in memory until you clear the map.
• The top of the list is always the same: cricket, the team names, good morning. Those are popular, not trending.
• A few thousand posts from one script can put any tag on the board.
• Each city needs its own board, so you need one map per city per window, and the cost multiplies.

The rest of this guide fixes each problem in turn. The counting problem goes to a sketch, popular-versus-rising goes to time decay, and spam goes to counting people instead of posts.

You need six words. Each gets a plain meaning and a link to the running example.

• Stream: data that keeps arriving and never ends, like the app's posts. You see each post once as it passes.
• Heavy hitter: an item that makes up a big share of the stream, for example any tag in more than 1 of every 1,000 posts.
• Top k: the k items with the highest counts, such as the 10 tags shown in the trending box.
• Hash function: a formula that turns any input, like a tag, into a number that looks random but is always the same for that input.
• Sketch: a small summary of a stream with a fixed size. It answers questions approximately, with a known error limit.
• Time decay: making old events count for less as time passes, so yesterday's buzz fades from today's board.

Trending topics system design is the plan for turning a firehose of posts into a short, fresh, per-region list of rising topics. It has four jobs: count, rank, decay and filter.

The public help page of X, formerly Twitter, describes the goal well. Its trends algorithm "identifies topics that are popular now, rather than topics that have been popular for a while". The same page says trends are tailored by who you follow, your interests and your location.

The diagram shows the pipeline for the running example. Read it left to right, and notice that the filter sits before the counters, not after them.

Reads are the easy half. Millions of people open the box, but they all read the same small cached list. The hard half is the write path, where every post must be counted as it arrives.

You can, for small apps, and you should start there. It stops working when the number of distinct tags, regions and windows multiplies past what one machine holds comfortably.

We ran a test stream of 10 lakh (1 million) posts. Tags were drawn from 2 lakh (200,000) possible tags with a long-tail pattern, where a few tags are very common and most are rare. The exact map held 88,030 distinct tags.

The sketch in the next section answered the same questions from 13,595 counters. That number stays fixed no matter how many new tags arrive. The exact map keeps growing with every new tag.

There is a second cost. When one tag gets thousands of updates a second, a single counter becomes a hot spot. The SevyDevy guide "Sharded Counters: Counting Likes at Scale" covers that fix. A sketch side-steps it, because each worker keeps its own sketch and the sketches add up later.

A Count-Min Sketch keeps a small grid of counters with d rows and w columns. Each tag adds one to one cell in every row, and its estimated count is the smallest of those cells.

It was published by Graham Cormode and S. Muthukrishnan in the Journal of Algorithms in 2005. The rest of this section follows their paper.

The tally sheet picture

Picture five tally sheets at a busy enquiry counter, each with only a few boxes. Every visitor's question is ticked once on each sheet, in a box chosen by a fixed rule for that sheet.

• The tally sheets are the rows of the sketch.
• The boxes are the columns, and each tick is a counter going up by one.
• The fixed rule for each sheet is that row's hash function.
• Two different questions sometimes share a box on one sheet. That box then counts both, so it is too high.
• To read a count, you look at the question's box on every sheet and trust the smallest tally.

Where the picture breaks: a real hash function scatters tags randomly, so sharing a box is luck, not a pattern. Also, the sketch never writes the tag's name anywhere. You cannot ask it which tags it has seen.

How an update and a query work

The diagram shows one post tagged monsoon arriving. Three of the rows are drawn to keep it readable.

The counts in the diagram are made up. The rule is real: an update touches d cells, and a query reads the same d cells and returns the minimum.

It cannot, as long as you only add. Every cell holds at least the tag's own count, so the smallest cell does too. The paper proves this as Theorem 1.

The same theorem bounds the overcount. Pick an error fraction eps and a failure chance delta. Set the width to e divided by eps, rounded up, where e is about 2.718. Set the depth to the natural log of 1 divided by delta, rounded up.

Then each estimate is at most eps times N too high, with probability at least 1 minus delta. Here N is the total number of posts counted so far. With eps 0.001 and 10 lakh posts, that limit is 1,000.

How big should the sketch be?

We ran our own sketch on the 10 lakh post stream at two sizes. Memory assumes 4 bytes per counter, and 1 KiB is 1,024 bytes.

No tag was ever undercounted, and no tag went past the promised limit. The promise must hold for any stream, so on this one the real errors sat well below it.

Now the catch. With the smaller sketch, tags that truly appeared 3 times were estimated between 51 and 108. A sketch is accurate for big tags and nearly useless for tiny ones.

Run it yourself

Beginners can skip the code and read the output below it. This code builds a sketch with one hash per row, of the form a times x plus b, modulo a large prime, then modulo the width. That is the pairwise-independent family the paper asks for. Tags are numbers here; in production you would hash the tag text first.

import math
import random
from collections import Counter

class CountMinSketch:
    def __init__(self, eps, delta, seed=1):
        self.w = math.ceil(math.e / eps)         # columns per row
        self.d = math.ceil(math.log(1 / delta))  # rows
        rng = random.Random(seed)
        self.p = 2 ** 61 - 1                      # a large prime
        self.ab = [(rng.randrange(1, self.p), rng.randrange(self.p))
                   for _ in range(self.d)]
        self.rows = [[0] * self.w for _ in range(self.d)]

    def _cols(self, item_id):
        return [((a * item_id + b) % self.p) % self.w for a, b in self.ab]

    def add(self, item_id, count=1):
        for row, col in zip(self.rows, self._cols(item_id)):
            row[col] += count

    def estimate(self, item_id):
        return min(row[col] for row, col in zip(self.rows, self._cols(item_id)))

rng = random.Random(7)
weights = [1 / r ** 1.1 for r in range(1, 200_001)]
stream = rng.choices(range(1, 200_001), weights=weights, k=1_000_000)
exact = Counter(stream)

cms = CountMinSketch(eps=0.001, delta=0.01)
for tag_id in stream:
    cms.add(tag_id)

print("width", cms.w, "depth", cms.d, "counters", cms.w * cms.d)
print("distinct tags", len(exact))
print("lowest error", min(cms.estimate(t) - n for t, n in exact.items()))
print("worst overcount", max(cms.estimate(t) - n for t, n in exact.items()))
print("tag 1: exact", exact[1], "estimate", cms.estimate(1))

On Python 3.13.17 it prints this. The run takes a few seconds, and the numbers are the same each time because the random seeds are fixed.

width 2719 depth 5 counters 13595
distinct tags 88030
lowest error 22
worst overcount 320
tag 1: exact 130868 estimate 130927

What just happened? The lowest error was 22, so all 88,030 tags were counted too high, never too low. The worst overcount was 320, well under the promised 1,000. The biggest tag was off by 59 out of about 1.3 lakh, under 0.05 percent.

You keep a short candidate list next to the sketch. The sketch cannot list its tags, because it never stores names, so a separate structure must remember which tags might be in the top k.

Option 1: a sketch plus a heap

The Count-Min paper's own method works for streams that only add. After each update, check the tag's estimate. If it passes a threshold, such as 1 in 1,000 posts, keep the tag in a min-heap, a structure that always knows its smallest member cheaply.

Option 2: Space-Saving, a list with no sketch at all

Space-Saving, by Metwally, Agrawal and El Abbadi, keeps exactly m tags with counts. A tag already on the list gets plus one. A new tag replaces the tag with the smallest count, takes that count plus one, and records the old count as its possible error.

The paper proves that counts never go below the truth. It also proves that any tag seen more often than the smallest count is on the list. That smallest count is at most N divided by m.

We ran it with 1,000 slots on 3 lakh posts. The smallest count was 136, under the limit of 300. Every tag above 300 was on the list, and the top 10 matched the exact top 10 in order.

Option 3: Misra-Gries, the older cousin

Misra and Gries published this idea in 1982. It keeps k minus 1 counters, where k sets the list size, not the 10 in a top 10. When a new tag arrives and the list is full, every counter drops by one, and counters that reach zero leave.

It undercounts instead of overcounting. Each drop removes k different mentions at once, so no tag can lose more than N divided by k. In our run with 999 counters, no tag lost more than 136, under that limit of 300. Their paper uses a second pass to get exact counts, which a live stream cannot do.

A topic is trending when its recent rate is much higher than its own normal rate. Big but steady topics, like cricket during a final, are popular, not trending.

So you keep two counts per tag. A short-memory count shows what is happening now. A long-memory count shows the tag's normal level. The trend score compares them.

A simple, workable score is the recent rate plus a small constant, divided by the baseline rate plus the same constant. The constant stops a tag going from 1 mention to 3 from looking like a 3x surge.

We tested this on two made-up tags over 10 hours, with a 5-minute half-life for the recent rate and a 60-minute half-life for the baseline. Half-life means the time after which an old mention counts half as much.

• A steady tag at 50 mentions a minute scored 1.00. Its recent rate and baseline were both 49.9 a minute.
• A tag that jumped from 5 to 40 mentions a minute, ten minutes ago, scored 2.62. Its recent rate was 31.2 and its baseline 8.8.

The rising tag wins even though it has fewer mentions, which matches the goal on the help page above. Its recent rate shows 31.2, not 40. Ten minutes is only two 5-minute half-lives, so the count has not caught up yet.

Beginners can stop here. You now know the whole design in outline: count with a sketch, keep a top-k list, and score by rate change. The sections below are for engineers who must build it.

You have two choices. Keep a ring of per-minute sketches and add up the last hour, or use exponential decay with a trick that never touches old counters.

Choice 1: sliding windows of small sketches

Keep one sketch per minute, all with the same width, depth and hash seeds. The last hour is the cell-by-cell sum of the last 60 sketches. When a minute leaves the window, you drop that sketch.

Adding sketches is exact. In our test, two regional sketches added together matched, cell for cell, a sketch built from both streams. The cost is 60 sketches of memory and a sum on every refresh.

Choice 2: exponential decay with forward decay

Exponential decay with a 10-minute half-life means a mention from 10 minutes ago counts half, and one from 20 minutes ago counts a quarter. Done naively, you would multiply every counter by a factor every second.

Forward decay, from a 2009 paper by Cormode, Shkapenyuk, Srivastava and Xu, avoids that. Pick a fixed start time called the landmark. Each new mention adds a weight that grows with its arrival time instead of shrinking with age.

At query time, you divide by the same growth factor for the current time. The paper shows this gives exactly the usual exponential decay. Old counters are never rewritten.

A Count-Min Sketch accepts any non-negative weight per update, so this works on a sketch too. In our run, the forward-decayed sketch matched a slow, brute-force decayed count to within floating-point rounding.

The overflow limit nobody mentions

The stored weights grow without limit. With a 10-minute half-life, they double every 10 minutes. A 64-bit float tops out at about 1.8 times 10 to the power 308, just under 2 to the power 1,024.

So a single weight overflows after 1,024 half-lives, about 170 hours, or a little over 7 days. In our test, 168 hours was safe and 171 hours overflowed. Counters hold sums of many weights, so they overflow somewhat sooner.

The paper's fix is to pick a new landmark and multiply every stored value by one factor, in a single pass. We did this and the answers did not change. Schedule it, for example every hour, and you never hit the limit.

Keep one sketch per city per window, then add city sketches together for the state and the country. This works only when every sketch uses the same width, depth and hash seeds.

With different seeds, the same tag lands in different cells, so the sums mean nothing. Our test code checks the seeds and refuses such a merge. Keep seeds in shared configuration, and never let workers pick their own.

Do not build the national top-k list by merging city top-k lists. A tag can be big across the country while ranking low in each city. Feed a national candidate list from all events, and check its estimates in the merged sketch.

Each region also needs its own thresholds. A tag with 500 mentions an hour may be huge in a small town and noise in Mumbai. Set the minimum volume per region from that region's own history.

Count accounts, not posts, and filter before counting. One script posting the same tag 5,000 times should add one, not 5,000.

In our toy run, one account posting a tag 5,000 times and 300 accounts posting another tag once each gave raw counts of 5,000 and 300. Counted as distinct accounts, they became 1 and 300.

The "seen recently" check needs to remember account and tag pairs for one window. A short-lived key per pair in a cache works. A Bloom filter per window uses less memory, but its false matches will drop a few genuine first posts.

Coordinated groups of fake accounts beat a per-account rule. Useful signals are many brand-new accounts on one tag, near-identical text, and posts arriving in tight bursts. Weight such events down rather than counting them fully.

Finally, keep a human or policy check before a new tag reaches the box. X's help page says it "may not allow or may temporarily prevent content from appearing in Trends until more context is available". Plan a blocklist and a review queue from day one.

Redis Open Source 8.0, released in May 2025, includes Count-min sketch and Top-k in all binary distributions. Earlier they came from the separate RedisBloom module. Four details matter, as of 24 October 2026.

The sizing difference changes memory. For error 0.0001 and probability 0.001, Redis builds 20,000 x 10 counters, about 781 KiB. The paper's formula gives 27,183 x 7, about 743 KiB.

The Top-K row is the one that bites trend builders. The decay comes from the HeavyKeeper paper, where it pushes small flows out of shared cells. It is not time decay. With the default 0.9, each colliding mention lowers a count of 100 with chance 0.9 to the power 100, about 0.003 percent. So a tag that was huge yesterday stays huge today.

So for trends, write each window to its own key, such as one Top-K per city per hour, and expire old keys. CMS.MERGE can add window sketches together, but only when width and depth match, and its weights are whole numbers.

They usually fail through a chain of small choices, not one bug. These are the links we would check first.

• Thresholds set as fixed numbers. The overcount limit is eps times N, so it grows with traffic. Recompute the threshold from the current total, as the Redis docs also advise.
• Trusting small counts. Our 3-mention tags read as 51 to 108. Hide any tag whose estimate is below a few times eps times N.
• Different hash seeds on different workers. Merges then give nonsense. Keep seeds in shared configuration.
• Counter overflow. Redis CMS counters stop at 4,294,967,295, and forward-decay floats overflow after about 1,024 half-lives.
• Counting after the fact. Spam that reached a sketch cannot be removed from a Redis CMS, which rejects negative increments.

The SevyDevy guide "Batch vs Stream Processing Explained: Late Data, Lambda and Kappa" covers how to run that daily batch check beside the live stream.

Lead with the definition of trending, then the counting structure, then decay, regions and abuse. Interviewers mostly test whether you know why exact counting fails and what a sketch costs you.

1. 1

   Define trending

   Say it means a rise against the tag's own baseline, per region, refreshed every minute or so. Ask about scale, regions and how fresh the list must be.

2. 2

   Estimate the load

   Work out posts per second and tags per post. Point out that reads are cheap because everyone reads one cached list.

3. 3

   Draw the pipeline

   Post API, event log, abuse filter, counting workers, aggregator, scorer, cache and read API. Put the filter before the counters.

4. 4

   Pick the counters

   Use a Count-Min Sketch for counts and Space-Saving or a heap for the top k. State the error limit, eps times N, and that it only overcounts.

5. 5

   Add decay and scoring

   Compare a short half-life rate with a long one. Mention ring buffers of minute sketches or forward decay, and its renormalisation.

6. 6

   Cover regions and abuse

   Merge city sketches with shared hash seeds. Count distinct accounts, weight new accounts down, and keep a review step.

7. 7

   Close with checks

   Compare against a nightly exact batch count and alert when the top 10 overlap drops.