Augmented resource graph for scoring resources

• US 8,386,495 B1
• Filed: 04/23/2010
• Issued: 02/26/2013
• Est. Priority Date: 04/23/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sandler, Mark M., Sivakumar, Dandapani
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US12/766,775
• Time in Patent Office: 1,040 Days
• Field of Search: 707/748, 707/798
• US Class Current: 707/748
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/953 Querying, e.g. by the use of web search engines

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for scoring resources. One method includes generating a resource graph, the graph including nodes representing resources, nodes representing queries, edges between nodes representing resources, and edges between nodes representing queries and nodes representing resources. The method further includes calculating a score for each of the resources, wherein the score for a particular resource is based on scores for resources represented by nodes with edges to the node representing particular resource in the graph and scores for queries represented by nodes that have an edge to the node representing particular resource in the graph, and ranking one or more of the resources in response to a first query received from a user based, at least in part, on the scores.

Claims

1. A computer-implemented method, comprising:

generating, by a data processing apparatus, a resource graph, the resource graph including nodes representing resources, nodes representing queries for resources, edges between nodes representing resources, and edges between nodes representing queries and nodes representing resources, wherein each edge between two nodes representing respective resources represents a link from one of the resources to another one of the resources and each edge between a node representing a resource and a node representing a query represents a user selection of a search result for the resource from search results responsive to the query;

calculating, by the data processing apparatus, a score for each of the resources, wherein the score for a particular resource is based, at least in part, on scores for resources represented by nodes with edges to a node representing the particular resource in the resource graph and scores for queries represented by nodes that have an edge to the node representing the particular resource in the resource graph; and

ranking, by the data processing apparatus, one or more of the resources in response to a query received from a user based, at least in part, on the scores for the resources;

wherein the resource graph further includes nodes representing user sessions and edges between nodes representing user sessions and nodes representing queries, wherein each edge between a node representing a user session and a node representing a query represents that a user associated with the user session submitted the query during the user session; and

wherein a score for a particular query is based, at least in part, on scores for user sessions represented by nodes with edges to a node representing the particular query in the resource graph.

2. The method of claim 1, wherein an edge between a first node and a second node representing respective resources is a directed edge from the first node representing one of the resources to the second node representing another one of the resources.

3. The method of claim 1, wherein each edge has an associated weight, and calculating a score for a resource is further based on weights of the edges from nodes to the node representing the resource.

4. The method of claim 3, wherein the weight of an edge between a node representing a first resource and a node representing a second resource is derived from a number of outbound links from the first resource to other resources.

5. The method of claim 3, wherein the weight of an edge between a node representing a query and a node representing a resource is derived from a quality of result statistic for the resource and the query.

6. The method of claim 5, wherein the quality of result statistic for the resource and the query is a click through rate for the resource and the query.

7. The method of claim 1, wherein calculating the score for each of the resources includes iteratively updating the scores of web resources and queries.

8. The method of claim 7, wherein calculating the score for each of the resources comprises:

initializing the score for each node in the resource graph, wherein the score for each node is one divided by a total number of nodes in the resource graph; and

iteratively updating the score for each node, wherein the updated score for each node is derived from a weighted average of scores of nodes with edges to the node.

9. A system, comprising:

a processor; and

a computer storage medium encoded with instructions, which, when executed by the processor, causes the processor to perform operations comprising;

generating a representation of a resource graph, the resource graph including nodes representing resources, nodes representing queries for resources, edges between nodes representing resources, and edges between nodes representing queries and nodes representing resources, wherein each edge between two nodes representing respective resources represents a link from one of the resources to another one of the resources and each edge between a node representing a resource and a node representing a query represents a user selection of a search result for the resource from search results responsive to the query;

calculating a score for each of the resources, wherein the score for a particular resource is based, at least in part, on scores for resources represented by nodes with edges to a node representing the particular resource in the resource graph and scores for queries represented by nodes that have an edge to the node representing the particular resource in the resource graph; and

ranking one or more of the resources in response to a query received from a user based, at least in part, on the scores for the resources;

wherein the resource graph further includes nodes representing user sessions and edges between nodes representing user sessions and nodes representing queries, wherein each edge between a node representing a user session and a node representing a query represents that a user associated with the user session submitted the query during the user session; and

wherein a score for a particular query is based, at least in part, on scores for user sessions represented by nodes with edges to a node representing the particular query in the resource graph.

10. The system of claim 9, wherein an edge between a first node and a second node representing respective resources is a directed edge from the first node representing one of the resources to the second node representing another one of the resources.

11. The system of claim 9, wherein each edge has an associated weight, and calculating a score for a resource is further based on weights of the edges from nodes to the node representing the resource.

12. The system of claim 11, wherein the weight of an edge between a node representing a first resource and a node representing a second resource is derived from a number of outbound links from the first resource to other resources.

13. The system of claim 11, wherein the weight of an edge between a node representing a query and a node representing a resource is derived from a quality of result statistic for the resource and the query.

14. The system of claim 13, wherein the quality of result statistic for the resource and the query is a click through rate for the resource and the query.

15. The system of claim 9, wherein calculating the score for each of the resources includes iteratively updating the scores of web resources and queries.

16. The system of claim 15, wherein calculating the score for each of the resources comprises:

initializing the score for each node in the resource graph, wherein the score for each node is one divided by a total number of nodes in the resource graph; and

iteratively updating the score for each node, wherein the updated score for each node is derived from a weighted average of scores of nodes with edges to the node.

17. A non-transitory computer-readable medium encoded with instructions, that when executed by a data processing apparatus, cause the data processing apparatus to perform operations comprising:

generating a representation of a resource graph, the resource graph including nodes representing resources, nodes representing queries for resources, edges between nodes representing resources, and edges between nodes representing queries and nodes representing resources, wherein each edge between two nodes representing respective resources represents a link from one of the resources to another one of the resources and each edge between a node representing a resource and a node representing a query represents a user selection of a search result for the resource from search results responsive to the query;

calculating a score for each of the resources, wherein the score for a particular resource is based, at least in part, on scores for resources represented by nodes with edges to a node representing the particular resource in the resource graph and scores for queries represented by nodes that have an edge to the node representing the particular resource in the resource graph; and

ranking one or more of the resources in response to a query received from a user based, at least in part, on the scores for the resources;

wherein the resource graph further includes nodes representing user sessions and edges between nodes representing user sessions and nodes representing queries, wherein each edge between a node representing a user session and a node representing a query represents that a user associated with the user session submitted the query during the user session; and

wherein a score for a particular query is based, at least in part, on scores for user sessions represented by nodes with edges to a node representing the particular query in the resource graph.

18. A computer-implemented method, comprising:

generating, by a data processing apparatus, a resource graph, the resource graph including nodes representing resources, nodes representing queries for resources, edges between nodes representing resources, and edges between nodes representing queries and nodes representing resources, wherein each edge between two nodes representing respective resources represents a link from one of the resources to another one of the resources and each edge between a node representing a resource and a node representing a query represents a user selection of a search result for the resource from search results responsive to the query;

calculating, by the data processing apparatus, a score for each of the resources, wherein the score for a particular resource is based, at least in part, on scores for resources represented by nodes with edges to a node representing the particular resource in the resource graph and scores for queries represented by nodes that have an edge to the node representing the particular resource in the resource graph; and

ranking, by the data processing apparatus, one or more of the resources in response to a query received from a user based, at least in part, on the scores for the resources;

wherein the resource graph further includes nodes representing users and edges between nodes representing users and nodes representing queries, wherein each edge between a node representing a user and a node representing a query represents that the user submitted the query; and

wherein a score for a particular query is based, at least in part, on scores for users represented by nodes with edges to a node representing the particular query in the resource graph.

19. A system, comprising:

a processor; and

a computer storage medium encoded with instructions, which, when executed by the processor, causes the processor to perform operations comprising;

generating a resource graph, the resource graph including nodes representing resources, nodes representing queries for resources, edges between nodes representing resources, and edges between nodes representing queries and nodes representing resources, wherein each edge between two nodes representing respective resources represents a link from one of the resources to another one of the resources and each edge between a node representing a resource and a node representing a query represents a user selection of a search result for the resource from search results responsive to the query;

calculating a score for each of the resources, wherein the score for a particular resource is based, at least in part, on scores for resources represented by nodes with edges to a node representing the particular resource in the resource graph and scores for queries represented by nodes that have an edge to the node representing the particular resource in the resource graph; and

ranking one or more of the resources in response to a query received from a user based, at least in part, on the scores for the resources;

wherein the resource graph further includes nodes representing users and edges between nodes representing users and nodes representing queries, wherein each edge between a node representing a user and a node representing a query represents that the user submitted the query; and

wherein a score for a particular query is based, at least in part, on scores for users represented by nodes with edges to a node representing the particular query in the resource graph.