[
https://issues.apache.org/jira/browse/HAMA-359?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13013536#comment-13013536
]
Thomas Jungblut commented on HAMA-359:
--------------------------------------
So I made up some algorithm's with the use of the slides. (not really optimal
cause it will require a sync step per current start vertex)
I'll write a bit more later.
For now I have set up a google code repository to store the things needed.
It is quite large because I already generated some test datasets with 2 bn
vertices based on cities in the world.
I wrote a mapper that will produce a random adjacency list that will be put
into hbase in the reduce step.
The table layout will be just a simple adjacency list like:
vertex : rowID of the out-vertex and weight : rowID of the next out-vertex and
its weight : etc.
So quite similar to David's approach, but much simpler.
Like the slides said, it should be quite difficult to distribute it even over
the clusters. I have a cool partitioning idea for that :D
So more about it later.
Here is the code site: (full repository is about 400mb large)
https://code.google.com/p/hama-shortest-paths/
Including a sequential A*, Dijkstra, some hardcoded (don't blame me!) example
graphs and a benchmark for it.
> Development of Shortest Path Finding Algorithm
> ----------------------------------------------
>
> Key: HAMA-359
> URL: https://issues.apache.org/jira/browse/HAMA-359
> Project: Hama
> Issue Type: New Feature
> Components: examples
> Affects Versions: 0.2.0
> Reporter: Edward J. Yoon
> Labels: gsoc, gsoc2011, mentor
> Fix For: 0.3.0
>
> Original Estimate: 2016h
> Remaining Estimate: 2016h
>
> The goal of this project is development of parallel algorithm for finding a
> Shortest Path using Hama BSP.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
