Patent ID: 8380723

Claim:
A method for use at a search engine arranged to receive queries and to provide search results for those queries, the search results comprising links to documents, the method comprising: receiving a query; accessing query reformulation data and using that data to create a query neighborhood around the received query, the query neighborhood being a graph data structure in memory comprising a node representing the received query and links connecting that node to other nodes representing-observed reformulations of that query; accessing evidence about queries related to the received query comprising a record of query-document pairs; using a processor to filter the query neighborhood by editing the graph data structure on the basis of the accessed evidence to produce and store in memory a reformulation graph; assigning weights to the reformulations in the reformulation graph using a random walk process that takes into account at least the number of times each reformulation was observed; clustering the nodes in the reformulation graph using the assigned weights; combining the weights of the queries in each cluster to obtain an importance score for that cluster; and using the reformulation graph to identify queries related to the received query.