How Twitter computes trending topics in real time

The Problem Statement

Interviewer: "Twitter shows trending topics within minutes of a major event breaking. With 500 million tweets per day, how does the system decide what is trending right now? Walk me through the architecture."

This question tests three things: whether you understand real-time stream processing at massive throughput, whether you know the difference between "popular" and "trending" (velocity vs volume), and whether you can reason about data quality problems like spam, bot manipulation, and geographic localization.

Most candidates describe a word counter. Strong candidates explain why raw counting is insufficient, how time-decay scoring separates a genuine spike from a permanently popular keyword, and how geographic segmentation surfaces local events that would be invisible in a global aggregate.

Clarifying the Scenario

You: "Before I start, I want to make sure I scope this correctly."

You: "When you say 'trending,' do you mean globally trending, or also location-specific trends like 'trending in New York' vs 'trending worldwide'?"

Interviewer: "Both. Start with global, then explain how you add geographic awareness."

You: "Got it. Should I focus on hashtags only, or also keywords and phrases that trend organically without a hashtag? For example, during an earthquake people tweet 'earthquake' without any hashtag."

Interviewer: "Both hashtags and organic keywords."

You: "One more: how fast does a trend need to surface? Seconds or minutes?"

Interviewer: "Minutes. A topic should appear in the trending list within 5 to 10 minutes of starting to spike."

You: "OK. I will structure my answer in four parts: the tweet ingestion pipeline, the count-min sketch layer for approximate frequency counting, the time-decay scoring model that prioritizes velocity over volume, and the geographic plus personalized trend ranking."

Approach

Break trending detection into five stages:

1. Ingestion: Consuming the tweet firehose (500M tweets/day, roughly 6,000 tweets/sec average, bursting to 50,000+ during events like the Super Bowl)
2. Extraction: Pulling hashtags, keywords, and named entities from each tweet
3. Approximate counting: Using a Count-Min Sketch to track frequency for millions of unique terms in sub-linear memory
4. Time-decay scoring: Applying exponential decay so recent mentions weigh more than older ones, making velocity the dominant signal
5. Ranking: Generating per-region and per-user trend lists using geographic segmentation and interest-based personalization

The fundamental insight is that "trending" does not mean "most mentioned." The word "the" appears in millions of tweets per day but never trends. "Good morning" spikes every day at 8am but is not interesting. Trending means the rate of mentions for a topic is significantly higher than its historical baseline right now. It is a velocity anomaly, not an absolute count.

This is a common interview mistake: designing a system that surfaces the most popular topics rather than the most accelerating ones. Justin Bieber would be permanently trending in that system. The correct system surfaces topics that are growing unusually fast compared to their own baseline.

The Architecture

The trending pipeline is a multi-stage stream processing system. Tweets flow from ingestion through extraction, approximate counting, scoring, filtering, and ranking before reaching the trending list.

Here is how a tweet becomes a trend:

Step 1: Ingestion. A user tweets "Just felt an earthquake in LA!" The tweet enters Kafka, partitioned for parallel processing across hundreds of stream workers.

Step 2: Extraction. The NLP pipeline extracts keywords: "earthquake," "LA." It detects the language (English), normalizes tokens (lowercase, stemming), and extracts any hashtags like #earthquake directly.

Step 3: Approximate counting. The Count-Min Sketch increments the approximate frequency for "earthquake" in the current time window. The Space-Saving algorithm checks whether "earthquake" qualifies as a top-K candidate based on its sketch count.

Step 4: Time-decay scoring. The decay function applies an exponential weight to recent mentions. The velocity score compares the decayed count against the historical baseline for "earthquake" at this hour and day of week. If the z-score exceeds 3.0, it qualifies as a trending candidate.

Step 5: Filtering. The spam filter checks whether the spike is driven by bots or coordinated accounts. The safety filter checks editorial policies. If the topic passes both, it enters the trending list.

Step 6: Ranking. The system generates separate trending lists for global, per-city, per-country, and personalized views. "Earthquake" trends in Los Angeles first (concentrated signal) before it trends globally (diluted by worldwide traffic).

Count-Min Sketch for Approximate Frequency Counting

This is the core data structure that makes trending detection possible at scale. You cannot maintain an exact counter for every keyword. With millions of unique tokens flowing through the pipeline, exact counting would require gigabytes of memory per worker. The Count-Min Sketch gives you approximate counts with fixed memory and O(1) operations.

A Count-Min Sketch is a 2D array of counters with d rows and w columns. Each row uses a different hash function. To increment a keyword, hash it with each of the d hash functions, and increment the counter at each resulting position. To query a keyword's count, hash it with all d functions and return the minimum value across all rows.

The key property: it can overestimate (due to hash collisions) but never underestimate. Taking the minimum across d rows minimizes the collision noise.

The memory math is important for interviews. A CMS with width w = 2^20 (about 1 million columns) and depth d = 5 uses 5 * 1M * 4 bytes = 20MB of memory. The error bound is ε = e/w ≈ 2.7 / 1M = 0.00027% of total count. For 6,000 tweets/sec over a 5-minute window (1.8M events), the maximum overestimation for any keyword is about 486 counts. For trending detection (where trending topics have tens of thousands of mentions), this error is negligible.

Combine CMS with the Space-Saving algorithm. CMS tracks approximate frequency for ALL keywords. Space-Saving maintains an exact top-K list (say, top 1,000) by evicting the least frequent candidate when a new one qualifies. This two-layer approach gives bounded memory for global counting and precise tracking for the trending candidates.

For the interview: say "Count-Min Sketch for approximate counting in fixed memory, Space-Saving for top-K candidate tracking, and the combination gives us bounded resources with good accuracy." That single sentence shows you know your data structures.

Windowing Choices for Real-Time Counting

The counting window determines both responsiveness and implementation cost:

• Tumbling windows use fixed, non-overlapping intervals such as 00:00–05:00 and 05:00–10:00. They are simple, but a spike that crosses a boundary is split across two windows and may look less significant in either one.
• Sliding windows evaluate the most recent N minutes continuously. They catch a spike regardless of when it starts, but require tracking or expiring events as they leave the window.
• Hopping windows update at a regular hop interval while covering a larger span. One-minute buckets summed over the last five buckets approximate a five-minute sliding window with bounded, minute-level granularity and are often a practical compromise.

The windowing choice should match the product latency target and the amount of state the stream processor can maintain. The anomaly detector can then apply time decay within the selected window.

Time-Decay Scoring: Why Velocity Matters More Than Volume

Raw counts are not enough. "Good morning" gets millions of mentions every day at 8am. "Justin Bieber" has a consistently high mention count. Neither is "trending" because they are always popular. A trending topic is one experiencing an unusual spike relative to its own historical baseline, and that spike must be recent.

Time-decay scoring solves both problems. Instead of counting raw mentions, each mention is weighted by how recent it is. A mention from 1 minute ago counts almost fully. A mention from 30 minutes ago counts half as much. A mention from 2 hours ago barely registers.

The exponential decay function:

decayed_count = Σ e^(-λ * (t_now - t_mention))

Where λ controls the half-life. With a half-life of 30 minutes (λ = ln(2) / 1800 ≈ 0.000385), a mention from 30 minutes ago contributes 0.5 to the count. A mention from 60 minutes ago contributes 0.25. This naturally makes the score velocity-sensitive: a burst of 10,000 mentions in the last 5 minutes produces a much higher decayed count than 10,000 mentions spread evenly across 2 hours.

I then compare the decayed count to a time-aware historical baseline. The baseline is computed from weeks of data, broken down by hour of day and day of week. "Good morning" has a high baseline at 8am on weekdays but a low baseline at 2am on Sundays. The anomaly detector uses the correct baseline for the current slot.

The z-score formula: z = (decayed_count - historical_mean) / historical_stddev

For "earthquake": z = (14,820 - 180) / 320 = 45.7. Massively anomalous. Trending.

For "good morning": z = (12,100 - 11,500) / 850 = 0.7. Normal daily variance. Not trending.

For "justin bieber": z = (3,200 - 2,900) / 320 = 0.94. Slightly above average. Not trending.

A minimum absolute count threshold (for example, 500 mentions in the current window) prevents obscure topics from trending just because their baseline is near zero. If a keyword normally gets 0 mentions and suddenly gets 5, the z-score is technically infinite, but 5 mentions do not constitute a meaningful trend.

The production approach uses hopping windows (a practical compromise). Divide time into small buckets (1 minute each), then sum the last 5 buckets to approximate a 5-minute sliding window. Apply time-decay weighting during the summation. The approximation error is at most 1 minute (the granularity of one bucket), which is fully acceptable for trending detection.

Geographic and Personalized Trend Ranking

A single global trending list misses local events entirely. An earthquake in LA generates massive tweet volume in Los Angeles but gets diluted in the worldwide aggregate. A political rally in London is meaningful to UK users but noise to users in Tokyo. Geographic segmentation is what makes trending useful.

The architecture maintains separate counting pipelines per region. Every tweet with location data (GPS, user profile city, IP geolocation) feeds into both the global pipeline and the appropriate regional pipeline. The anomaly detector runs independently at each level.

For a user in Los Angeles, the trending tab shows a blended list: local trends first (trending in LA), then national (trending in US), then global (trending worldwide). Each level runs its own anomaly detection with its own baselines, so a topic can trend at one level without trending at others.

Personalized trending adds another dimension. Instead of showing the same list to every user in LA, the system overlays the user's interest graph. Topics trending among accounts you follow are weighted higher in your personal view. If you follow earthquake monitoring accounts and LA news, "earthquake" surfaces with higher priority. If you follow gaming accounts, a trending game release might rank ahead of the earthquake in your personalized tab.

The personalization signal is lightweight: compute the fraction of your followed accounts contributing to the trend. If 20% of accounts you follow are tweeting about #WorldCup, that trend gets a personalization boost. Crucially, this is computed at read time (when you load the trending tab), not write time (when each tweet is processed). This keeps the write path simple with no per-user counting overhead.

About 30% of tweets have precise location data (GPS or tagged location). For the remaining 70%, the system infers location from the user's profile city, IP geolocation, and language signals. A user tweeting in Marathi about Mumbai traffic is almost certainly in Mumbai, even without GPS. The inference is imperfect but sufficient for regional trending.

Spam and Manipulation Filtering

Without filtering, a trending list can be manipulated by bot amplification, coordinated inauthentic behavior, or hashtag hijacking. The signals are different: a single account may tweet at an implausible rate, many otherwise ordinary accounts may publish the same topic in a narrow interval, or unrelated promotional content may attach itself to a legitimate trend.

An illustrative filtering pipeline is:

Account age, follower/following patterns, posting velocity, content uniqueness, and engagement diversity can contribute to a reputation or organic score. A weighted count is safer than a binary bot/not-bot decision: a low-reputation account can contribute less without making classification errors catastrophic. Coordination signals—many accounts with little prior interaction posting the same phrase within a short window—can trigger review or reduce the affected tweets' weights. Thresholds such as “20 posts per minute” or a particular coordination score are workload-specific and must be tuned against false positives.

The Tricky Parts

1. Cold start for new keywords. When a completely new term appears (a coined hashtag, a newly famous name), it has no historical baseline. The z-score formula fails (division by zero). The fix: maintain a default baseline computed as the average stats across all keywords of similar frequency class. For brand-new keywords, use this default. Switch to the keyword-specific baseline once 24 to 48 hours of data accumulates. The default is kept deliberately low so genuinely viral new terms still produce high z-scores.

2. The "always popular" masking problem. "Good morning" has such a high baseline at 8am that even a genuine viral meme involving those words only produces a z-score of 2.5. The fix: add a velocity z-score measuring acceleration (second derivative of the count). A viral meme causes acceleration that the normal daily ramp-up does not. Combine static z-score and velocity z-score with an OR gate.

3. Trending decay and removal. Once a topic stops accelerating, it should stop trending. But users expect trends to persist for a few hours. The system uses a "trending half-life": once the z-score drops below threshold, the topic remains with decaying priority for 2 to 4 hours. Topics that peaked at #1 globally get a longer half-life than those that barely crossed the threshold.

4. Keyword ambiguity. "Apple" could mean the company, the fruit, or a person. Without disambiguation, unrelated spikes conflate into one trend. The mitigation: co-occurrence analysis clusters tweets by context words, and hashtags serve as disambiguation anchors. The UI can present subtopics when users click through.

5. Retweets vs original mentions. A single tweet retweeted 50,000 times is one opinion amplified, not 50,000 independent signals. Weight original tweets at 1.0 and retweets at 0.1 to 0.3 to measure genuine breadth of conversation rather than amplification depth.

6. Coordinated manipulation. Bot networks tweet the same hashtag from thousands of low-reputation accounts. The fix: each tweet is weighted by account reputation, and a coordination detector flags synchronized bursts from socially unconnected accounts. This degrades gracefully even if some bots are misclassified.

What Most People Get Wrong

How to Communicate This in an Interview

Here is a concise way to say this:

"Trending detection is fundamentally an anomaly detection problem, not a counting problem. The word 'the' appears in millions of tweets but never trends. Trending means the mention rate for a topic is significantly above its own historical baseline right now.

The pipeline has four stages. First, tweets enter Kafka partitioned for parallel processing. An NLP pipeline extracts hashtags, keywords, and named entities.

Second, use a Count-Min Sketch for approximate frequency counting across millions of unique keywords in fixed memory, about 20MB per sketch. The sketch feeds a Space-Saving top-K algorithm that maintains the 1,000 most frequent candidates.

Third, I apply time-decay scoring with an exponential half-life of about 30 minutes, so recent mentions weigh much more. I compute a z-score for each candidate by comparing its decayed count against its historical baseline for this hour and day of week. A z-score above 3.0 with a minimum absolute count qualifies as trending.

Fourth, run this entire pipeline independently at city, country, and global levels. An earthquake in LA trends locally within minutes even if it takes longer to register globally. Personalization overlays the user's follow graph to re-rank each user's blended geographic list.

Spam filtering weights each tweet by account reputation. Bot campaigns with thousands of low-reputation accounts produce minimal signal that rarely triggers trending."

Interview Cheat Sheet

• Trigger: "How does Twitter detect trends?" say "Anomaly detection over time-decayed counts, not raw popularity. Z-score against historical baselines. Z above 3.0 with minimum absolute count equals trending."
• Count-Min Sketch: "Probabilistic data structure for approximate frequency counting. Fixed memory (20MB), O(1) update and query. Overestimates but never underestimates. Pair with Space-Saving for top-K candidates."
• Time-decay: "Exponential decay with 30-minute half-life. A mention from 1 minute ago counts almost fully. A mention from 2 hours ago barely registers. Makes the score velocity-sensitive by design."
• Velocity vs volume: "Trending means 'growing unusually fast' not 'frequently mentioned.' Justin Bieber would permanently trend in a volume-based system. Time-decay plus z-score scoring fixes this."
• Sliding windows: "Hopping windows: 1-minute buckets summed over 5-minute spans. Avoids the boundary spike problem of tumbling windows where a spike straddling two buckets is undercounted in both."
• Spam filtering: "Weight tweets by account reputation score (0 to 1). Bot accounts contribute minimally. Coordination detection flags synchronized bursts from socially unconnected accounts."
• Geographic trending: "Separate counting pipelines per city, country, and global. Independent anomaly detection at each level. A topic can trend locally without trending globally."
• Personalization: "At read time, re-rank the geographic trend list using the user's follow graph. Topics trending among accounts you follow rank higher. No per-user write-time computation."
• Stream processing: "Apache Flink or Storm for real-time counting. Kafka for ingestion buffering. Never batch MapReduce for trending detection."
• New keywords: "No historical baseline for new terms. Use a default baseline from similar-frequency keywords until 24 to 48 hours of keyword-specific data accumulates."

Test Your Understanding

Quick Recap

1. Trending is an anomaly detection problem, not a counting problem. "Popular" and "trending" are fundamentally different: trending means growing unusually fast relative to a topic's own baseline.
2. Count-Min Sketch provides approximate frequency counting with fixed memory and O(1) operations. Space-Saving maintains the top-K candidates for anomaly evaluation.
3. Time-decay scoring with exponential decay (30-minute half-life) makes the count velocity-sensitive: recent mentions dominate, old mentions fade naturally.
4. Z-score anomaly detection compares decayed counts against time-aware baselines (hour of day, day of week) to surface genuinely unusual spikes.
5. Spam filtering weights each tweet by account reputation (0 to 1) and uses coordination detection to suppress synchronized bot campaigns.
6. Geographic trending runs independent counting pipelines per city, country, and global with separate anomaly detection at each level.
7. Personalized trending re-ranks the geographic list at read time using the user's follow graph, requiring no per-user write-time computation.
8. Stream processing (Flink, Storm, Kafka Streams) is mandatory for sub-minute latency. Batch processing is never acceptable for trending detection.

Related Concepts

• Stream processing architectures covers how Apache Flink, Storm, and Kafka Streams distribute stateful computation across workers, handle exactly-once semantics, and manage checkpointing for fault tolerance.
• Probabilistic data structures explains the mathematical foundations of Count-Min Sketch, Bloom filters, and HyperLogLog, including error bounds, hash function selection, and conservative update optimization.
• Time-series anomaly detection covers the broader field of detecting outliers in temporal data, including EWMA, Holt-Winters, and seasonal decomposition methods beyond simple z-scores.
• Content moderation and trust and safety explains how platforms detect coordinated inauthentic behavior, bot networks, and manipulation campaigns at scale.
• Real-time personalization covers recommendation systems that overlay global signals with per-user interest graphs to produce individualized feeds and trend lists.