Patent ID: 6792419
Filing Date: 2004-09-14
Classification: G06F,Y10S

Abstract:
A method for searching for one or more hyperlinked documents that match a search query, comprising:generating a directed graph from a crawl through one or more documents, the directed graph having one or more nodes representing one or more documents traversed during the crawl and one or more directed edges wherein each directed edge represents a hyperlink from a first document to a second document; determining a weight for each document in the directed graph based on a stochastic backoff process that includes: determining a forward probability 1-p(A) for each possible forward step from a node A that is taken by following a directed edge, wherein the forward step includes proceeding from node A to a node B where there is a directed edge from node A to node B; determining a backward probability p(A) for each possible backward step from the node A, wherein the backward step is taken by using a browser back button, the backward step including proceeding from the node A to a previously visited node from which a forward step was taken into node A; and determining a pair probability p(A,B) for a directed graph from the node A to the node B such that a sum of all p(A,B) is 1; retrieving one or more documents that match a search query; and generating a ranking of the documents based on the determined weight such that relative ranks of the documents depend on the forward probability 1-p(A), the backward probability p(A), and the pair probability p(A,B) associated with each document.