[
https://issues.apache.org/jira/browse/MADLIB-992?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15755724#comment-15755724
]
Orhan Kislal commented on MADLIB-992:
-------------------------------------
Here is the pseudocode of our implementation. I'll include this in the tex
files for the design documentation.
{code}
|V|: Number of vertices
start = Source vertex (input)
edge: (src,dest,val). The edges of the graph.
cur: id -> (val,parent). The intermediate SSSP results.
toupdate: iter -> (id -> (val,parent)). The set of updates.
toupdate(0) = (start,0,start)
1:for every i in 0..|V|-1
2: for every tuple t in toupdate(i)
3: for every edge e where e.src = t.id
4: local_val = e.val + t.val
5: if local_val < toupdate(i+1,e.dest).val
6: toupdate(i+1,dest) = (local_val,e.src)
7: for every tuple t in toupdate(i+1)
8: if t.val < cur(t.id).val
9: cur(t.id) = (t.val,t.parent)
10: return cur
{code}
Changes from the standart Bellman-Ford algorithm:
- 2: We only check the vertices that have been updated in the last iteration.
- 5: At each iteration, we update a given vertex only one time. This means the
toupdate set cannot contain multiple records for the same vertex which requires
the comparison with the existing value.
This is not a 1-to-1 pseudocode for the implementation since we don't compare
the `toupdate` table records one by one but calculate the overall minimum. In
addition, the comparison with `cur` values take place earlier to reduce the
number of tuples in the `toupdate` table.
> Graph - single source shortest path
> -----------------------------------
>
> Key: MADLIB-992
> URL: https://issues.apache.org/jira/browse/MADLIB-992
> Project: Apache MADlib
> Issue Type: New Feature
> Components: Module: Graph
> Reporter: Frank McQuillan
> Assignee: Orhan Kislal
> Fix For: v1.10
>
> Attachments: SSSP graph scale tests.pdf, sssp-grails.sql
>
>
> Background
> The academic foundation for this work comes in part from Jignesh Patel at
> University of Wisconsin-Madison, who has researched how to build graph
> engines in relational databases [1][2][3].
> Story
> As a MADlib developer, I want to investigate how to implement shortest path
> in an efficient and scaleable way.
> Acceptance
> 1) Interface defined
> 2) Design document updated
> 3) Form an opinion on whether 1GB workaround can be useful to improve graph
> size and performance from https://issues.apache.org/jira/browse/MADLIB-991
> 4) Functional tests complete
> 5) Scaleability tests complete
> References
> [1] Grails paper
> http://pages.cs.wisc.edu/~jignesh/publ/Grail.pdf
> [2] Grails deck
> http://pages.cs.wisc.edu/~jignesh/publ/Grail-slides.pdf
> [3] Grails repo
> https://github.com/UWQuickstep/Grail
> [4] Grails generated SQL for shortest patch (attached)
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
