Patent ID: 7739264

Claim:
A method for generating one or more related queries with respect to a given query, the method comprising: receiving a query comprising one or more terms; segmenting the received query into one or more segments; generating a corpus of candidate reformulations, wherein generating the corpus of candidate reformulations comprises generating a pair of successive queries or segments of one or more terms; identifying one or more queries or terms from the corpus of candidate reformulations related to the received query; generating one or more related queries on the basis of the identified one or more queries or terms from the corpus of candidate reformulations; calculating probability scores for the one or more related queries indicating an extent to which the one or more related queries are related to the received query, the calculating the probability score for a related query including modifying the probability score associated with the related query based upon an analysis of one or more features associated with the received query and the related query; and selecting one or more of the related queries with probability scores exceeding a given threshold; wherein modifying the probability score associated with a given related query comprises: performing an analysis of one or more query log features associated with the related query and the received query, including identifying a frequency with which a plurality of users rewrite the received query into the related query as indicated by a plurality of query logs from a plurality of users; performing an analysis of one or more location features associated with the related query and the received query, including identifying a location specified by the received query; identifying a location specified by the related query; and identifying an extent to which the location specified by the received query is related to the location specified by the related query; and modifying the probability score based upon the analysis.