Posts

Showing posts from May, 2011

The Mountain

GSoC, Implementation of single source shortest path using Hama

Despite the Hama project [1] is still under heavy construction, one of my GSoC students has excellently (or aggressively) finished implementing [2] his plan, "Implementation of single source shortest path using Hama" [3] and also started to contribute improvements to the Hama project. He used an algorithm described in Google Pregel paper [4] , and it works nicely on my 2-rack cluster (512 cores). But, more surprisingly, he is just 19 years old! :o When I was 19 years old? JDK 1.1 released. I first met the monster called Diablo [5] . I ridden bike. (-_-;) 1. http://incubator.apache.org/hama 2. https://issues.apache.org/jira/browse/HAMA-359 3. http://wiki.apache.org/hama/SSSP 4. http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf 5. http://en.wikipedia.org/wiki/Diablo_(video_game)

[Note] Dijkstra's vs. Bellman-Ford

Dijkstra's : relax each edge exactly once (can't handle negative weights) Bellman-Ford : relax each edge |V| -1 times Anything else?