[
https://issues.apache.org/jira/browse/HAMA-359?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13019231#comment-13019231
]
Thomas Jungblut commented on HAMA-359:
--------------------------------------
{noformat} There is one thing, I think, the proposal has a lack of detailed
description of parallelization strategy.{noformat}
Thank you Edward for your feedback, I'm going to describe it a bit clearer.
But I want to outline that this task strongly depends on the design of the
input system. -> https://issues.apache.org/jira/browse/HAMA-258
What are the things we currently have:
* HBase table as input
** this will be partitioned (key mod sizeOfCluster?)
** every vertex is reachable with it's ID, the groom where the data actually is
stored can be back-translated from the ID of a vertex.
* Through the partitioning phase we receive a subgraph on each groom
* Main algorithm works like this
** We are broadcasting a start-vertex ID to the grooms
** Now every groom is calculating the distances from the start-vertex to each
adjacent vertex
** Each groom holds a local minimum and sends this to a master task.
** The master will review these minimas and broadcasts the new start-vertex
(the global minimum) to the grooms.
** Repeat until we can not update anymore.
* Output of each groom with its own vertex -> ancestor to reconstruct the
shortest paths. Maybe we can store the actual weight, too.
Maybe we need to merge these. If you have a better idea of how we can deal with
subgraphs more efficiently, you're welcome to give me a hint ;)
> 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
> Assignee: 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
