Maybe a look at Pegasus [1] could be helpful. This framework uses a so called "Generalized Iterative Matrix Vector Multiplication" to implement a variety of graph algorithms on MapReduce. They did not include shortest distance computation, but the Belman Ford algorithm is also be implementable with their model.
Best, Sebastian [1] http://www.cs.cmu.edu/~pegasus/ On 20.04.2012 19:37, Mike Spreitzer wrote: > I am trying to understand the comparative virtues of map-reduce vs. the > programming model found in Pregel. Both cite BSP as inspiration, but > Pregel's model includes iteration, per-component state, and selective > activation --- all of which are absent in map-reduce. While one could > implement Pregel (or pretty much anything else) on top of Hadoop with > sufficient additional client code, I am trying to compare the quality of > doing that with instead taking the programming model of Pregel, simplified > to apply to key-value data instead of graphs, as the fundamental > abstraction and building other things (as needed/desired) on top of that. > As noted in other replies, the additional features of the Pregel model > look like they could be very beneficial for solving the problem I posed. I > would like to do an actual comparison. So I want to know the best way to > solve this maintenance problem using map-reduce. > > Thanks, > Mike > > > > From: Saikat Kanjilal <[email protected]> > To: "[email protected]" <[email protected]> > Cc: "[email protected]" <[email protected]> > Date: 04/20/2012 12:21 PM > Subject: Re: shortest-path maintenance > > > > Is it a requirement to use map reduce? Also how does mahout play into > this? Potentially you could build mappers that could reference an in > memory graph and have an API that pre calculates dijkstra or astar up > front. You could then add or remove a node as part of the reduce process > that references this graph and recalculates dijkstra or astar in a closed > feedback loop. However its not obvious to me that mapreduce is the > appropriate tool to do this. > > Some more context into the problem and how mahout fits in would be great. > > Sent from my iPhone > > > >
