Return-Path: X-Original-To: apmail-mahout-user-archive@www.apache.org Delivered-To: apmail-mahout-user-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 45D8C9F2A for ; Sun, 22 Apr 2012 09:37:33 +0000 (UTC) Received: (qmail 88607 invoked by uid 500); 22 Apr 2012 09:37:31 -0000 Delivered-To: apmail-mahout-user-archive@mahout.apache.org Received: (qmail 88334 invoked by uid 500); 22 Apr 2012 09:37:26 -0000 Mailing-List: contact user-help@mahout.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: user@mahout.apache.org Delivered-To: mailing list user@mahout.apache.org Received: (qmail 88282 invoked by uid 99); 22 Apr 2012 09:37:23 -0000 Received: from minotaur.apache.org (HELO minotaur.apache.org) (140.211.11.9) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 22 Apr 2012 09:37:23 +0000 Received: from localhost (HELO mail-yx0-f170.google.com) (127.0.0.1) (smtp-auth username ssc, mechanism plain) by minotaur.apache.org (qpsmtpd/0.29) with ESMTP; Sun, 22 Apr 2012 09:37:23 +0000 Received: by yenl5 with SMTP id l5so10302958yen.1 for ; Sun, 22 Apr 2012 02:37:22 -0700 (PDT) MIME-Version: 1.0 Received: by 10.236.181.133 with SMTP id l5mr6280302yhm.71.1335087442630; Sun, 22 Apr 2012 02:37:22 -0700 (PDT) Received: by 10.236.207.104 with HTTP; Sun, 22 Apr 2012 02:37:22 -0700 (PDT) In-Reply-To: References: <4F91A2E1.5030609@apache.org> Date: Sun, 22 Apr 2012 11:37:22 +0200 Message-ID: Subject: Re: shortest-path maintenance From: Sebastian Schelter To: user@mahout.apache.org Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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 : > Yes, the GIM-V of Pegasus can be used to implement Belman Ford. =C2=A0But= I do > not see how selective activation can happen in that approach. =C2=A0I see > nothing like selective activation in GIM-V. > > Regards, > Mike > > > > From: =C2=A0 Sebastian Schelter > To: =C2=A0 =C2=A0 user@mahout.apache.org > Date: =C2=A0 04/20/2012 01:55 PM > Subject: =C2=A0 =C2=A0 =C2=A0 =C2=A0Re: 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/ > > >