Patent Document ID: 9703871
Application ID: 12847510

Base Claim:
1. A computer-implemented method comprising: receiving a query comprising a first plurality of terms in a first order; dividing the query into a plurality of combinations of n-grams, wherein each n-gram is a subset of terms of the first plurality of terms, the subset of terms being in a same order as in the first plurality of terms; for each combination of n-grams: determining, for each n-gram of the combination, a probability that the n-gram is a related phrase, wherein an n-gram is a related phrase when the terms of the n-gram are found together in training data more frequently than those terms would be found together if they were not associated with each other; summing the probabilities of each n-gram of the combination; identifying a particular combination of each combination of n-grams based on the summed probability of each combination, wherein the particular combination has a largest summed probability of the combinations; identifying first and second components of the query based on the identified particular combination, wherein each component comprises one or more of the terms of the query in order and the two components do not share a term from the query, and wherein the terms of the first component appear in the first order before the terms of the second component in the query; determining, for each of the first and second components, a plurality of different respective component refinements; and combining the component refinements to create a plurality of candidate query refinements for the query, including, for each candidate query refinement: combining a first component refinement for the first component with a second component refinement for the second component to create the candidate query refinement for the query, the candidate query refinement comprising a second plurality of terms in a second order and different from the first plurality of terms in the first order, wherein the first component refinement appears in the second order before the second component refinement in the query refinement; filtering the candidate query refinements of the query to create a subset of the candidate query refinements for the query, including: determining for each candidate query refinement a score based on a click-through rate for the candidate query refinement, wherein the click-through rate is a total number of clicks on a plurality of documents presented in response to the candidate query refinement divided by a total number of impressions for the plurality of documents presented in response to the candidate query refinement; and removing from the plurality of candidate query refinements any candidate query refinements having a score not satisfying a threshold score; and providing a plurality of the subset of the candidate query refinements in response to receiving the query.

---

Claim 3:
3. The method of claim 1 , wherein determining the probability that the n-gram is a related phrase is based on a function of the n-gram's relative frequency in training data.