Patent ID: 8423538
Filing Date: 2013-04-16
Classification: G06F,G06N

Abstract:
1. A computer-implemented method, comprising: identifying a plurality of refinements R(q) of a first search query q, each refinement r∈R(q) being a search query that follows the first search query q in a session of queries submitted to a search system; identifying a document set D(r) of each of the refinements r, the document set of a refinement being the documents d that are search results presented in response to the refinement by the search system and that have received user selection while being presented as the search results; building a representation of a graph G for the first search query q, wherein the graph G has a node for the first search query q, a node for each of the refinements r, and a node for each document din the document sets of the refinements, and wherein the graph G has edges from the first search query node q to each of the refinements nodes r, edges from the first search query q to each document d in the respective document set D(q) of the first search query q, edges from each refinement r to each document in the respective document set D(r) of the refinement r, and edges from each refinement r to each co-occurring query of the refinement r; building a transition probability matrix P for the graph G that includes the following elements: where M is a numerical parameter between 0 and 1; calculating a visit probability vector for each refinement in the plurality of refinements R(q) from the transition probability matrix P, where each vector has elements representing a probability for each document in the document set D(q) and the document sets of the refinements R(q); and clustering the refinements into refinement clusters by partitioning the visit probability vectors into proper subsets; and deriving one or more search suggestions for the first search query based on the refinement clusters.