1. A method comprising: determining prefixes, infixes and postfixes of unique queries in a log of past queries submitted to one or more search engines, wherein an infix of a particular unique query is a sequence of one or more terms occurring between a prefix at a beginning of the particular unique query and a postfix at an end of the particular query; identifying a plurality of groups of queries, wherein the queries in each group have matching prefixes, matching postfixes and different infixes; forming for each group of queries a respective query template by selecting the matched prefix and the matched postfix of the queries in the group; reformulating the query templates into corresponding canonical representations using canonicalization rules; identifying a first group of queries in the plurality of groups of queries that has a query template canonical representation matching that of a second group of queries in the plurality of groups of queries; identifying candidate phrases based at least in part on similarity scores between the infixes of the queries in the second group and the candidate phrases; selecting infixes of one or more queries in the first group of queries, wherein selecting the infixes of queries in the first group includes creating a list of the candidate phrases based on the similarity scores between the infixes of the queries in the second group and the candidate phrases, and selecting only infixes of queries in the first group which appear in the list of candidate phrases; creating one or more inferred queries by adding the selected infixes to the query template of the second group of queries; and storing the inferred queries for use as query suggestions.