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 including at least one dwell time associated with one or more search results and a number of links clicked; 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.