13. A method implemented by data processing apparatus, the method comprising: obtaining a search query; selecting one or more previously submitted queries as candidate refinement queries, wherein the selected previously submitted queries were submitted by a user during a first search session following submission of the search query, and wherein the first search session includes search queries submitted by the user during a first period of time; selecting one or more terms from training data as candidate refinement queries, wherein a respective right context of each of the selected terms in the training data includes at least one word in a right context of the search query, and wherein a respective left context of each of the selected terms in the training data includes at least one word in a left context of the search query; determining one or more categories for the search query; determining one or more categories for each of the candidate refinement queries; determining a respective first score for each of the candidate refinement queries, wherein determining the respective first score for the candidate refinement query comprises adjusting the respective first score for the candidate refinement queries based on a number of categories shared between the candidate refinement query and the search query; and identifying as query refinements for the search query one or more of the candidate refinement queries based on the first scores.
13. A method implemented by data processing apparatus, the method comprising: obtaining a search query; selecting one or more previously submitted queries as candidate refinement queries, wherein the selected previously submitted queries were submitted by a user during a first search session following submission of the search query, and wherein the first search session includes search queries submitted by the user during a first period of time; selecting one or more terms from training data as candidate refinement queries, wherein a respective right context of each of the selected terms in the training data includes at least one word in a right context of the search query, and wherein a respective left context of each of the selected terms in the training data includes at least one word in a left context of the search query; determining one or more categories for the search query; determining one or more categories for each of the candidate refinement queries; determining a respective first score for each of the candidate refinement queries, wherein determining the respective first score for the candidate refinement query comprises adjusting the respective first score for the candidate refinement queries based on a number of categories shared between the candidate refinement query and the search query; and identifying as query refinements for the search query one or more of the candidate refinement queries based on the first scores. 22. The method of claim 13 , further comprising: determining that the search query is parent-like; and selecting only candidate refinement queries that are parent-like as being refinement queries for the search query.