Section 9: Yesterday's Counts, This Morning's News - Deep Dive: Ranking and Freshness

Executive Summary: Section 8's prefix index stores fifteen query ids per node; this section decides which fifteen. The base score is a time-decayed count of submitted searches, each user counted once per query per day, with a 7-day half-life, rebuilt daily. A streaming trending path catches spikes within 10 minutes (p95) and ships a delta of at most 100K queries every minute. Each serving node merges the two at query time, and the client puts personal history on top. Trending is the freshest signal and also the easiest one to attack, so it gets the strictest gates.

The interviewer taps the trie on the board. "Every node has a top-15. Ranked by what?"

The Base Score: Counting With a Half-Life

"By how many people actually submitted the query, with recent days weighted more," you answer, and you write the formula:

score(q) = Σ over days d in the 30-day window:  count(q, d) × 0.5^(age_days / 7)

Here count(q, d) is the number of distinct hashed users who submitted q on day d: each user counts at most once per query per day, so repeating a search adds nothing. The daily batch computes it exactly with a group-by on (day, locale, query, user).

Today's count weighs 1.0. One from 7 days ago weighs 0.5, 14 days ago 0.25, and 21 days ago 0.125. Then you show why the decay is there, with illustrative en-US numbers, treating each week's counts as one bucket at ages 0, 7, 14 and 21 days:

A raw count puts the old phone first. The decayed score puts the new one first, which is what people typing iphone 1 want right now. All-time counts would be worse still.

"Why seven days?" "It's a dial. Shorter makes the dropdown jumpy; longer keeps last month's news around. Seven days smooths weekly cycles and retires stale queries in a few weeks. Faster spikes are the trending path's job."

What gets counted matters as much as the formula: submitted searches and suggestion selections, never raw keystrokes, or chicago mar becomes a "popular query" (D8). Day one adds one small, bounded boost or penalty from how often a shown suggestion gets picked. You name the catch: shown items get picked because they are shown, so this feedback loop is kept weak on purpose.

Key Insight: Precomputing top-K per node (D1) only works because the score is a property of the query alone. The same decayed number is right for every prefix that leads to the query, so the builder can compute it once and spread it up the trie in a single bottom-up pass.

Quick check before moving on: