3 ms·
Google has published a very short paper about a program, called Pregel, which expresses graph algorithms using message passing between vertices. Apparently its
by pjscott 16y ago
Google has published a very short paper about a program, called Pregel, which expresses graph algorithms using message passing between vertices. Apparently its scaling doesn't suck:
http://www.royans.net/arch/pregel-googles-other-data-processing-infrastructure/ http://www.royans.net/arch/pregel-googles-other-data-process...
They do try to group related vertices as much as possible, but if edges span computers, that's okay too. I assume that it works best when the interconnect between computers is low-latency, though.
- jbooth 16y agoYeah, but that is hard. You probably need some clustering heuristic that autolocates nodes and edges on hosts near their neighbors, a way to distribute that work, and even still, the latency penalty for the cross-node lookups will be significant and require a lot of optimization. Unless they've thought of some brilliantly simple method that I haven't, which is certainly possible.
- pjscott 16y agoThey don't have a brilliantly simple method; just graph-specific heuristics. The example they gave in the paper was that, if they've got a graph corresponding to web pages and the links between them, to group together vertices representing pages from the same domain. So, yeah, they're going to have a lot of cross-node messaging.