Scalable system for determining short paths within web link network

• US 9,400,849 B1
• Filed: 08/29/2014
• Issued: 07/26/2016
• Est. Priority Date: 08/08/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Alpert, Jesse Louis, Hajaj, Nissan
• Primary Examiner(s): Hershley, Mark E
• Application Number:
  US14/473,563
• Time in Patent Office: 697 Days
• Field of Search: 707/737, 707/755
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/35 Clustering; Classification
• 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/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

Systems and methods for finding multiple shortest paths. A directed graph representing web resources and links are divided into shards, each shard comprising a portion of the graph representing multiple web resources. Each of the shards is assigned to a server, and a distance table is calculated in parallel for each of the web resources in each shard using a nearest seed computation in the server to which the shard was assigned.

Claims

1. A system, comprising:

multiple computer servers programmed to perform operations comprising;

dividing a directed graph representing web resources and links into shards, wherein the directed graph comprises nodes representing web resources, wherein some of the nodes in the directed graph are designated as seeds, and wherein each shard comprises a respective portion of the graph representing multiple web resources and links associated with the multiple web resources;

assigning each of the shards to a respective server, including assigning, to each of the respective servers, data describing the links associated with the multiple web resources represented by the nodes in the portion of the graph corresponding to the shard assigned to the server; and

determining, by each of the servers and using the data describing the links assigned to the server;

n nearest seeds to each of the nodes in the portion of the graph corresponding to the shard assigned to the server, and

respective distances from each of the nodes in the portion of the graph corresponding to the shard assigned to the server to each of the n nearest seeds to the node, wherein n is a positive integer greater than one.

2. The system of claim 1, the operations further comprising:

ranking the web resources based on the distances.

3. The system of claim 1, wherein n is equal to three.

4. The system of claim 1, wherein the n nearest seeds to the node are those nodes designated as seeds having the n shortest distances to the node.

5. The system of claim 1, the operations further comprising:

storing, by each of the servers, the distances in a distance table maintained by the server.

6. The system of claim 1, the operations further comprising:

receiving data identifying some of the web resources represented by nodes in the directed graph as seed resources; and

designating the nodes representing the identified web resources as seeds.

7. The system of claim 1, wherein the data describing the links associated with the multiple web resources represented by the nodes in the portion of the graph corresponding to the shard assigned to the server comprises data identifying, for each web resource represented by a node in the portion of the graph corresponding to the shard assigned to the server, any outgoing links from the web resource and a target node linked to by each outgoing link.

8. A method performed by multiple computer servers, the method comprising:

dividing a directed graph representing web resources and links into shards, wherein the directed graph comprises nodes representing web resources, wherein some of the nodes in the directed graph are designated as seeds, and wherein each shard comprises a respective portion of the graph representing multiple web resources and links associated with the multiple web resources;

assigning each of the shards to a respective server, including assigning, to each of the respective servers, data describing the links associated with the multiple web resources represented by the nodes in the portion of the graph corresponding to the shard assigned to the server; and

determining, by each of the servers and using the data describing the links assigned to the server;

n nearest seeds to each of the nodes in the portion of the graph corresponding to the shard assigned to the server, and

respective distances from each of the nodes in the portion of the graph corresponding to the shard assigned to the server to each of the n nearest seeds to the node, wherein n is a positive integer greater than one.

9. The method of claim 8, further comprising:

ranking the web resources based on the distances.

10. The method of claim 8, wherein n is equal to three.

11. The method of claim 8, wherein the n nearest seeds to the node are those nodes designated as seeds having the n shortest distances to the node.

12. The method of claim 8, further comprising:

storing, by each of the servers, the distances in a distance table maintained by the server.

13. The method of claim 8, further comprising:

receiving data identifying some of the web resources represented by nodes in the directed graph as seed resources; and

designating the nodes representing the identified web resources as seeds.

14. The method of claim 8, wherein the data describing the links associated with the multiple web resources represented by the nodes in the portion of the graph corresponding to the shard assigned to the server comprises data identifying, for each web resource represented by a node in the portion of the graph corresponding to the shard assigned to the server, any outgoing links from the web resource and a target node linked to by each outgoing link.

15. One or more non-transitory computer storage media storing instructions that, when executed by multiple computer servers, cause the computer servers to perform operations comprising:

dividing a directed graph representing web resources and links into shards, wherein the directed graph comprises nodes representing web resources, wherein some of the nodes in the directed graph are designated as seeds, and wherein each shard comprises a respective portion of the graph representing multiple web resources and links associated with the multiple web resources;

assigning each of the shards to a respective server, including assigning, to each of the respective servers, data describing the links associated with the multiple web resources represented by the nodes in the portion of the graph corresponding to the shard assigned to the server; and

determining, by each of the servers and using the data describing the links assigned to the server;

n nearest seeds to each of the nodes in the portion of the graph corresponding to the shard assigned to the server, and

respective distances from each of the nodes in the portion of the graph corresponding to the shard assigned to the server to each of the n nearest seeds to the node, wherein n is a positive integer greater than one.

16. The one or more non-transitory computer storage media of claim 15, the operations further comprising:

ranking the web resources based on the distances.

17. The one or more non-transitory computer storage media of claim 15, wherein the n nearest seeds to the node are those nodes designated as seeds having the n shortest distances to the node.

18. The one or more non-transitory computer storage media of claim 15, the operations further comprising:

storing, by each of the servers, the distances in a distance table maintained by the server.

19. The one or more non-transitory computer storage media of claim 15, the operations further comprising:

receiving data identifying some of the web resources represented by nodes in the directed graph as seed resources; and

designating the nodes representing the identified web resources as seeds.

20. The one or more non-transitory computer storage media of claim 15, wherein the data describing the links associated with the multiple web resources represented by the nodes in the portion of the graph corresponding to the shard assigned to the server comprises data identifying, for each web resource represented by a node in the portion of the graph corresponding to the shard assigned to the server, any outgoing links from the web resource and a target node linked to by each outgoing link.