1. A method of selecting at least one variant of a given query suggestion, including: determining, using canonicalization rules, canonical representations of the given query suggestion and unique queries that do not include the given query suggestion as a prefix, wherein the unique queries are existing queries submitted to one or more search engines in the past; comparing the canonical representation of the given query suggestion to the canonical representations of the unique queries to produce similarity scores between the given query suggestion and the unique queries, the similarity scores based on similarity between the canonical representation of the given query suggestion and the canonical representations of the unique queries; selecting one or more of the unique queries having similarity scores that satisfy a threshold as candidate variants of the given query suggestion, wherein selecting the one or more of the unique queries as candidate variants includes selecting at least one unique query which has a canonical representation identical to that of the given query suggestion; selecting one or more of the candidate variants as selected variants of the given query suggestion using query utility scores for the candidate variants, wherein a query utility score for a candidate variant is based on user response to the candidate variant during one or more prior queries; and storing data associating the given query suggestion with the selected variants for use in determining an alternative suggestion for the given query suggestion from among the selected variants.
2. The method of claim 1 , wherein selecting the one or more of the candidate variants as selected variants includes selecting candidate variants having query utility scores greater than that of the given query suggestion.