Method And System For Generating A Hyperlink-Click Graph
First Claim
Patent Images
1. A method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising using a processor to perform the steps of:
- generating, from the plurality of search queries and a first subset of the plurality of documents, a click graph representative of relationships between the plurality of search queries and the documents comprising the first subset of documents;
generating, from a second subset of the documents, a hyperlink graph representative of relationships between the documents in the second subset;
generating a hyperlink-click graph from the union of the hyperlink and click graphs, wherein;
each node corresponds either to one of the plurality of documents or one of the plurality of search queries;
each directed edge between documents corresponds to the relationships defined in the hyperlink graph; and
each undirected edge between documents and search queries corresponds to the relationships defined in the click graph;
conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; and
for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.
9 Assignments
0 Petitions
Accused Products
Abstract
A method of ascribing scores to web documents and search queries generates a hyperlink-click graph by taking the union of the hyperlink and click graphs, takes a random walk on the hyperlink-click graph, and associates the transition probabilities resulting from the random walk with scores for each of the documents and search queries.
67 Citations
22 Claims
-
1. A method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising using a processor to perform the steps of:
-
generating, from the plurality of search queries and a first subset of the plurality of documents, a click graph representative of relationships between the plurality of search queries and the documents comprising the first subset of documents; generating, from a second subset of the documents, a hyperlink graph representative of relationships between the documents in the second subset; generating a hyperlink-click graph from the union of the hyperlink and click graphs, wherein; each node corresponds either to one of the plurality of documents or one of the plurality of search queries; each directed edge between documents corresponds to the relationships defined in the hyperlink graph; and each undirected edge between documents and search queries corresponds to the relationships defined in the click graph; conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; and for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising using a processor to perform the steps of:
-
generating a hyperlink-click graph wherein; each node corresponds either to one of the plurality of documents or to one of the plurality of search queries; each directed edge corresponds to a relationship between two of the plurality of documents; and each undirected edge corresponds to a relationship between one of the plurality of search queries and one of the plurality of documents, which document is associated with a search result related to the search query; conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.
-
-
11. A system, comprising:
-
a click graph generator to generate, from a plurality of search queries and a first subset of a plurality of documents, a click graph representative of relationships between the plurality of search queries and the documents comprising the first subset of documents; a hyperlink graph generator to generate, from a second subset of the documents, a hyperlink graph representative of relationships between the documents in the second subset; a hyperlink-click graph generator to generate a hyperlink-click graph from the union of the hyperlink and click graphs, wherein; each node corresponds either to one of the plurality of documents or one of the plurality of search queries; each directed edge between documents corresponds to the relationships defined in the hyperlink graph; and each undirected edge between documents and search queries corresponds to the relationships defined in the click graph; and a random walker to; conduct a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; and associate, for each of the plurality of documents and search queries, a transition probability resulting from the random walk with a score.
-
-
12. A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising:
-
generating, from the plurality of search queries and a first subset of the plurality of documents, a click graph representative of relationships between the plurality of search queries and the documents comprising the first subset of documents; generating, from a second subset of the documents, a hyperlink graph representative of relationships between the documents in the second subset; generating a hyperlink-click graph from the union of the hyperlink and click graphs, wherein; each node corresponds either to one of the plurality of documents or one of the plurality of search queries; each directed edge between documents corresponds to the relationships defined in the hyperlink graph; and each undirected edge between documents and search queries corresponds to the relationships defined in the click graph; conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; and for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising:
-
generating a hyperlink-click graph wherein; each node corresponds either to one of the plurality of documents or to one of the plurality of search queries; each directed edge corresponds to a relationship between two of the plurality of documents; and each undirected edge corresponds to a relationship between one of the plurality of search queries and one of the plurality of documents, which document is associated with a search result related to the search query; conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.
-
-
22. A method of generating a hyperlink-click graph, wherein the hyperlink-click graph comprises a plurality of nodes, a plurality of directed edges, and a plurality of undirected edges, said method comprising using a processor to perform the step of:
taking the union of a hyperlink graph and a click graph, such that; each resultant node corresponds either to one of a plurality of documents or to one of a plurality of search queries; each resultant directed edge corresponds to a relationship between two of the plurality of documents; and each resultant undirected edge corresponds to a relationship between one of a plurality of search queries and one of a plurality of documents, which document is associated with a search result related to the search query.
Specification