[jira] [Commented] (GIRAPH-1254) A linear round complexity algorithm for unweighted, exact all pairs shortest path (APSP)

["mohit (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/GIRAPH-1254?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17514165#comment-17514165 ] 

mohit commented on GIRAPH-1254:
-------------------------------

Here is the pseudo code for the Algorithm.
 # Select an arbitrary vertex, call it vertex v.
 # start a distributed algorithm from vertex v, to build a BFS T_v
 # Send a pebble P on T_v
 # Distributed protocol to be run on each vertex x
 ## while P reaches x
 ### if P visits x for the first time then
 #### wait one time slot ('iterative step' in Giraph lingo) 
 #### start a BFS at T_x

Constructing a BFS tree:  basically message propagation.

Note that in the above psudo code, I did not explicitly mention about computing APSP, but when BFS trees are computing, it is implict on computation of BFS tree, the level of a vertex in a BFS tree is equal to the length of APSP. 

Run time guarantee: O(n) rounds (iterative steps), with low bandwidth messages exchanged between only adjacent vertices. 

 

// any feedback is welcome.

 

 

> A linear round complexity algorithm for unweighted, exact all pairs shortest path (APSP)
> ----------------------------------------------------------------------------------------
>
>                 Key: GIRAPH-1254
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-1254
>             Project: Giraph
>          Issue Type: New Feature
>          Components: examples
>    Affects Versions: 1.3.0
>            Reporter: mohit
>            Priority: Minor
>
> In the theory community (mainly targeting PODC, SODA, FOCS, and STOC), several graph algorithms for APSP have been developed in the abstract model of vertex-centric computation. These distinguished themselves upon
>  # weighted vs unweighted
>  # randomized vs deterministic
>  # exact vs approximation
>  # permission for message passing, and message size
>  ## between only adjacent vertices
>  ## between any two vertices in the graph
> This Jira is to implement a simple linear-time algorithm for APSP (discussed on the dev list). An algorithm for a fundamental problem like APSP has several practical use cases, for example in developing large scale recommender systems. This implementation would also lead the way forward for some recent results claiming poly log round complexity for various graph algorithms in the aforementioned graph model.



--
This message was sent by Atlassian Jira
(v8.20.1#820001)