Graph Algorithms Sources

[Apurv Verma <da...@gmail.com>]

Hii,
 Are there any sources for learning about implementing graph algorithms in
the BSP framework.


--
thanks and regards,

Apurv

Re: Graph Algorithms Sources

[Thomas Jungblut <th...@googlemail.com>]

Hi Apurv,

actually, none that I know of.
Everything I really know about distributed graph processing comes from that
paper:
http://www.umiacs.umd.edu/~jimmylin/publications/Lin_Schatz_MLG2010.pdf

It explains how to run graph algorithms with mapreduce. It uses a technique
called message passing, where you "pass" messages over iterations of
mapreduce jobs over the filesystem.
Since Hama provides this messaging mechanism natively and without the
overhead of scheduling MapReduce jobs all over the place, Hama should be
faster than any MapReduce implementation.

However, there may exist some paradigm to solve graph algorithms I (and we)
aren't aware of, which is even more optimal. I haven't the time to research
this.

For tutorials, I think my blog is a good place to start from. [1] I have
coded, SSSP,Pagerank and somekind of graph-exploration which is just a
mindist search in a graph. Just browse through them, on the bottom right
side there are some mappings for each month.
There may exist other people writing about BSP, but mostly papers without
concrete implementations.
It takes some time to get the gist of the algorithms, but afterwards you
will solve every graph problems with messaging because it is just cool ;)

Good luck, I'll help you if you don't understand something.

Best Regards from Germany,
Thomas

[1] http://codingwiththomas.blogspot.com/

2011/12/13 Apurv Verma <da...@gmail.com>

> Hii,
>  Are there any sources for learning about implementing graph algorithms in
> the BSP framework.
>
>
> --
> thanks and regards,
>
> Apurv
>
>
>
>
>


-- 
Thomas Jungblut
Berlin <th...@gmail.com>