6. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising: receiving a pair of terms that includes a term and a candidate synonym of the term; determining that the terms of the pair have been identified as being potentially non-synonymous; evaluating the pair of terms using one or more penalty criteria that are only applied to terms that are identified as being potentially non-synonymous, comprising determining a quantity of switches that have occurred between queries that include the term and queries that include the candidate synonym of the term; selecting a first threshold if the pair of terms satisfies the penalty criteria, or a second threshold if the pair of terms does not satisfy the penalty criteria, wherein the first threshold is a same threshold that is applied to pairs of terms that are not identified as being potentially non-synonymous, and wherein the second threshold is higher than the first threshold; and determining that the terms of the pair are synonyms when the selected threshold is exceeded.
9. The computer storage medium of claim 6 , wherein evaluating the pair of terms using one or more penalty criteria comprises: determining a first quantity, representing a number of times that users of a search engine have submitted queries that include the term; and calculating a ratio by dividing the quantity of switches by the first quantity; and determining whether the ratio satisfies a predetermined comparison threshold.