1. One or more computer storage media storing computer-executable instructions for performing a method for identifying query rewriting replacement terms, the method comprising: receiving a list of related string pairs, each pair comprising a first string and a second string, wherein the first string of each related string pair is a user search query extracted from user click log data, and wherein the user click log data includes data for one or more search query sessions; for one or more of the related string pairs, providing the string pair as inputs to a statistical machine translation model that: identifies one or more pairs of corresponding terms, each pair of corresponding terms including a first term from the first string and a second term from the second string, and calculates a probability of relatedness for each of the one or more pairs of corresponding terms; and upon determining that the calculated probability of relatedness of a pair of corresponding terms exceeds a threshold: characterizing the second term as a query term replacement for the first term, and incorporating the first term, the second term, and the probability of relatedness for the pair into a query rewriting candidate database.