Parallelizing graph computations
View Patent ↗Performing an operation on a web graph is disclosed. A plurality of computers is initialized. The web graph is divided into portions. The portions are distributed to the plurality of computers. The results of the computation are propagated from the plurality of the computers to each of the plurality of computers. Optionally, a coordinator is used.
1. A method of performing an operation on a web graph comprising:
initializing a plurality of computers;
dividing, using at least one processor, the web graph into a plurality of portions, wherein the web graph includes a representation of the link structure of a collection of documents, and wherein a first document included in the collection of documents has at least one inlink and at least one outlink;
distributing the plurality of portions to a plurality of computers, wherein distributing includes:
distributing a first portion in the plurality of the portions to a first computer included in the plurality of computers;
wherein the first portion includes a representation of the at least one inlink of the first document and does not include a representation of the at least one outlink of the first document; and
propagating results of computations performed by the plurality of the computers to each of the plurality of computers.
2. The method of claim 1 wherein the computation is a state computation.
3. The method of claim 1 wherein the computation is a value computation.
4. The method of claim 1 wherein the initializing includes initializing a computation vector.
5. The method of claim 1 wherein the computation is a vector multiplication.
6. The method of claim 1 wherein the results are propagated via the Transmission Control Protocol.
7. The method of claim 1 wherein the results are propagated via the User Datagram Protocol.
8. The method of claim 1 further comprising receiving results of the computations from the plurality of computers.
9. The method of claim 1 wherein the results of the computation are distributed at least in part by a coordinator.
10. The method of claim 1 wherein the portions are distributed to a plurality of computers at least in part by a coordinator.
11. The method of claim 1 wherein multiple iterations of distributing and propagating are performed until convergence is reached.
12. A system for performing an operation on a web graph comprising:
a first computer participant; and
a second computer participant, wherein the second computer participant is configured to:
receive a portion of the web graph, wherein the web graph includes a representation of the link structure of a collection of documents;
perform a computation; and
propagate results of the computation to the first computer participant;
wherein a first document included in the collection of documents has at least one inlink and at least one outlink, and wherein the portion received by the second computer participant includes a representation of the at least one inlink of the first document and does not include a representation of the at least one outlink of the first document.
13. The system of claim 12 wherein the computation is a state computation.
14. The system of claim 12 wherein the computation is a value computation.
15. The system of claim 12 wherein the computation is a vector multiplication.
16. The system of claim 12 wherein the plurality of participants are configured to iteratively perform a plurality of computations and propagate results until convergence is reached.
17. The system of claim 12 further comprising a coordinator.
18. The system of claim 17 wherein the coordinator is configured to communicate with the plurality of participants via the Transmission Control Protocol.
19. The method of claim 17 wherein the coordinator is configured to communicate with the plurality of participants via the User Datagram Protocol.
20. A computer program product for performing an operation on a web graph, the computer program product comprising a computer readable storage medium and comprising computer instructions for:
initializing a plurality of computers;
dividing the web graph into a plurality of portions, wherein the web graph includes a representation of the link structure of a collection of documents, and wherein a first document included in the collection of documents has at least one inlink and at least one outlink;
distributing the plurality of portions to a plurality of computers, wherein distributing includes:
distributing a first portion in the plurality of portions to a first computer included in the plurality of computers;
wherein the first portion includes a representation of the at least one inlink of the first document and does not include a representation of the at least one outlink of the first document; and
propagating results of computations performed by the plurality of the computers to each of the plurality of computers.