mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sebastian Schelter <...@apache.org>
Subject Re: shortest-path maintenance
Date Sun, 22 Apr 2012 09:37:22 GMT
There is nothing like that in Pegasus. The computational dependencies
of something like Belman-Ford are however very sparse and clearly
defniied, so you would have to modify the join that computes a
matrix-vector mulitplication to include the vertices that need to be
recomputed (all those where one incident neighbor changed in the
previous iteration).

--sebastian

2012/4/21 Mike Spreitzer <mspreitz@us.ibm.com>:
> Yes, the GIM-V of Pegasus can be used to implement Belman Ford.  But I do
> not see how selective activation can happen in that approach.  I see
> nothing like selective activation in GIM-V.
>
> Regards,
> Mike
>
>
>
> From:   Sebastian Schelter <ssc@apache.org>
> To:     user@mahout.apache.org
> Date:   04/20/2012 01:55 PM
> Subject:        Re: shortest-path maintenance
>
>
>
> 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/
>
>
>

Mime
View raw message