Hamburg, a graph computing framework on Hadoop

As mentioned ago, I've been forming up the Hamburg project with Hyunsik Choi. Let's see more detail in the diagram of computing method of Hamburg based on BSP model.

Each worker will process the data fragments stored locally. And then, We can do bulk synchronization using collected communication data. The 'Computation' and 'Bulk synchronization' can be performed iteratively, Data for synchronization can be compressed to reduce network usage.

Plainly, It aims to improve the performance of traverse operations in Graph computing. For example, to explores all the neighboring nodes from the root node using Map/Reduce (FYI, Breadth-First Search (BFS) & MapReduce), We need a lot of iterations to get next vertex per-hop time.

If (same condition as before) do BFS using Hamburg, It will cause a lowering the cost of iterations. Let's assume the graph looks like presented below:

The graph was stored in Hbase on distributed system as above. The root is 1. Then, we need only one 'Bulk synchronization' between server2 and server3 with Hamburg. Rests will be calculated on local machine.

Almost graph algorithms are similar with this case.

Updated - 26 August, 2009 : See also, Inference anatomy of the Google Pregel