1. A computer-implemented method performed by a data processing apparatus, the method comprising: selecting one or more query pairs of queries from user sessions, each query pair being a first query and a second query that were submitted as separate queries during a search session with up to a maximum number of intervening queries between the first query and the second query, each first and second query including at least one term; for each query pair: selecting one or more term pairs from the query pair, each term pair being a first term in the first query and a second term in the second query; and determining a co-occurrence value for each selected term pair; aggregating the co-occurrence values determined for each selected term pair over all selected query pairs; determining, for each unique term pair of the selected term pairs, a probability that the unique term pair co-occurs; and determining, for each unique term pair, a transition cost based on the probability that the unique term pair co-occurs, each transition cost indicative of a cost of transitioning from a first term in a first query to a second term in a second query.