[
https://issues.apache.org/jira/browse/MADLIB-1099?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16051110#comment-16051110
]
Frank McQuillan commented on MADLIB-1099:
-----------------------------------------
I attached a screen shot of some perf testing; this is an expensive algo as we
know.
This is what I wrote in the user docs for APSP:
"APSP is an expensive algorithm for run-time because it finds the shortest path
between all nodes in the graph. The worst case run-time for this implementation
is O(V^2 * E) where V is the number of vertices and E is the number of edges.
In practice, run-time will be generally be much less than this, depending on
the graph."
> Graph - all pairs shortest path grouping
> ----------------------------------------
>
> Key: MADLIB-1099
> URL: https://issues.apache.org/jira/browse/MADLIB-1099
> Project: Apache MADlib
> Issue Type: Improvement
> Components: Module: Graph
> Reporter: Frank McQuillan
> Assignee: Frank McQuillan
> Fix For: v1.12
>
> Attachments: screenshot-1.png
>
>
> Story
> As a MADlib developer, I want to implement grouping for all pairs shortest
> path in an efficient and scaleable manner, so that I can compute other
> measures that use APSP (eg., centrality measures).
> Acceptance
> 1) Grouping param in interface
> 2) Documentation and on-line help
> 3) IC and Tinc tests
> 4) Scale testing done
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
