hama-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Jungblut (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HAMA-359) Development of Shortest Path Finding Algorithm
Date Wed, 13 Apr 2011 06:40:05 GMT

    [ 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. ->

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

View raw message