Under the Hood: Mining Query Relationships
Related searches (e.g. searching "distributed systems" and seeing suggestions for "Raft consensus", "CAP theorem", and "vector clocks") help users navigate complex information spaces. These recommendations are mined from collective user behavior across millions of search sessions.
Query-Click Bipartite Graph Architecture
Under the Hood: Mining Algorithms
- Session Co-occurrence Mining: If thousands of users search for Query A followed by Query B within the same 30-minute browsing session, the two queries share high temporal affinity. Pairwise pointwise mutual information (PMI) quantifies this association while filtering out trivial coincidences.
- Random Walks on Bipartite Graphs (SimRank / Personalized PageRank): Construct a bipartite graph connecting search queries to the web pages clicked by users. Performing random walks with restarts reveals queries that share high structural overlap in click destinations, identifying high-quality conceptual synonyms.
Worked example: PMI beats raw counts
From 10 million sessions: query A, "kafka architecture", appears in 100,000 sessions. Candidate B, "kafka partitions", appears in 50,000 sessions and co-occurs with A in 5,000. Candidate C, "facebook", appears in 1,000,000 sessions and co-occurs with A in 12,000.
| Candidate | Co-occurrences | P(A and X) divided by P(A) x P(X) | PMI, log2 |
|---|---|---|---|
| kafka partitions | 5,000 | 0.0005 divided by 0.00005 = 10 | 3.32 |
| 12,000 | 0.0012 divided by 0.001 = 1.2 | 0.26 |
Raw counts would suggest "facebook"; PMI correctly picks "kafka partitions". Because PMI inflates very rare pairs, production systems add a minimum support threshold, for example at least 50 co-occurrences, or use a smoothed variant.
Signals and their trade-offs
| Signal | Captures | Weakness |
|---|---|---|
| Session reformulation, A then B within 30 minutes | Refinement and next-step intent | Sparse for rare queries; noisy when users switch tasks |
| Shared clicks on the query-URL bipartite graph | Same-meaning queries | Tends to find synonyms rather than useful next steps |
| Query embeddings | Coverage of the long tail | Can suggest plausible but unhelpful queries |
| Editorial lists | Control for high-value queries | Does not scale |
Serving
A nightly or hourly job computes, for each of the top few million normalised queries, a ranked list of about 8 related queries and writes it to a key-value store. At request time the service normalises the query, does one lookup, and falls back to an embedding nearest-neighbour lookup for misses. Filtering is essential: remove suggestions with no results, adult or unsafe content, and anything that could reveal an individual's searches, which is why a minimum count across distinct users is enforced.
Evaluation
Measure suggestion click-through rate, and more importantly whether sessions that used a related search end in success, such as a purchase or a long dwell click. A suggestion that gets clicks but leads to abandonment is a distraction. Offline, sample query and suggestion pairs for human rating of relevance and diversity, and check that suggestions are not near duplicates of the original.