[
https://issues.apache.org/jira/browse/MADLIB-992?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15703416#comment-15703416
]
Orhan Kislal commented on MADLIB-992:
-------------------------------------
Here is the interface I am planning to use for this function. Please let me
know if you have any questions and/or comments.
MADLIB_SCHEMA.graph_sssp(
vertex_table TEXT,
vertex_id TEXT,
edge_table TEXT,
edge_args TEXT,
source_vertex INT,
out_table TEXT
)
vertex_table: Name of the table that contains the vertex data. Has to contain
the column specified in the vertex_id parameter.
vertex_id (default = "id"): Name of the column containing the vertex ids in the
vertex table.
edge_table: Name of the table that contains the edge data. Has to contain the
columns specified in the edge_args parameter.
edge_args: A comma-delimited string containing multiple named arguments of the
form "name=value".
The following parameters are supported for this string argument:
src (default = "src"): Name of the column containing the source vertex
ids in the edge table.
dest (default = "dest"): Name of the column containing the destination
vertex ids in the edge table.
weight (default = "weight"): Name of the column containing the weight
of edges in the edge table.
source_vertex: The source vertex id for the algorithm to start. This vertex id
has to exist in the vertex_id column of vertex_table.
out_table: Name of the table to store the result of SSSP. It will contain a row
for every vertex from vertex_table and have the following columns:
vertex_id : The id for the destination. Will use the input parameter
(vertex_id) for column naming.
weight : The total weight of the shortest path from the source vertex
to this particular vertex. Will use the input parameter (weight) for column
naming.
parent : The parent of this vertex in the shortest path from source.
> 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)
