Patent ID: 8417692

Claim:
A computer-implemented method performed by a data processing apparatus, the method comprising: selecting 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 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; determining a co-occurrence value for each selected term pair, the determining comprising: identifying a first set of terms included in the first query and not included in the second query, identifying a second set of terms included the second query and not included in the first query, and for the selected term pair, in response to identifying the first term is an element of the first set and the second term is an element of the second set, determining the co-occurrence value based on the size of the first set and the size of the second set; and determining transition costs based on the co-occurrence values for term pairs of the query pairs, 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.