1. A method 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, by one or more computers, 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.