Twitter Trending Topics

Real-time Analytics

Design trending topics for a social network: find the terms people are suddenly talking about more than usual, per location, within a minute or two, and keep spam out.

Overview

Trending topics is the short list of what people are talking about right now. The obvious design, count every hashtag and show the ten biggest, gives the wrong answer: the biggest terms are the same every day (a sports league, a pop star, 'good morning'). Twitter said as much when it explained its Trends in 2010: the list is produced by an algorithm that looks for topics being talked about more right now than they were before, it favors novelty over popularity, and a very popular term may not trend if its conversation is not speeding up fast enough relative to its normal level.

So this problem is about change detection, not ranking by size. For every term, the system must know its normal rate, notice when the current rate breaks well above it, check that the surge comes from many different people, and publish a list per location within a minute or two. Ranking by decayed volume is a different problem, covered in the YouTube Top K Trending topic.

Questions to ask first

What is a topic? — Hashtags and short phrases (1 to 3 words) extracted from public posts
Trending means? — Rising fast against its own normal level, not the largest
How fresh? — A new trend appears within about 2 minutes
Where? — A worldwide list plus lists for about 500 countries and cities
Personalized? — Location first; 'for you' reranking is optional
What must never trend? — Spam, coordinated boosting, and content that breaks the rules

What you will be able to do

Explain why trending is velocity against a baseline, and show it with numbers.
Design a streaming counter per term, per minute, per location, including hot keys and late events.
Score terms with a moving-average baseline, and explain why the score adapts to small and large terms.
Keep bots and coordinated campaigns out with distinct-author counts and weights.
Serve per-location lists cheaply and say how the system fails safely.

Key concepts

Velocity vs volume
Per-term baseline
Moving average and variance
Minute buckets
Event time and watermarks
Distinct authors (HyperLogLog)
Hot-key pre-aggregation
Term normalization and clustering
Per-location lists
Precomputed serving

Functional requirements

Extract hashtags and short phrases from every public post
Detect terms rising well above their normal rate, per location and worldwide
Show a ranked list of about 10 to 30 trends per location, with approximate post counts
Group different spellings of one story into one trend
Exclude spam, coordinated boosting and rule-breaking terms; allow manual removal
Show a trend's recent volume over time

Non-functional requirements

A new trend appears within about 2 minutes of the surge (a target we chose)
The trends API answers in under about 50 ms from cache (a target we chose)
Counting keeps up with at least 5× the average post rate
If the pipeline stalls, the last good lists keep being served, marked by their age
Counts may be approximate; the trend decision must not be driven by a handful of accounts

Interview questions

Why not just show the most-mentioned hashtags?
How do you compute the baseline for millions of terms?
Why divide by the variance rather than use now ÷ normal?
A bot network pushes a hashtag. What stops it?
Everyone posts about one event. How do you avoid a hot partition?
How fast is a trend detected, end to end?
How is this different from YouTube-style top K trending?
What happens when the pipeline stalls?