Scalable system for determining short paths within web link network
View Patent ↗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.
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.