[MADLIB-992] Graph - single source shortest path

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: v1.10
• Component/s: Module: Graph
• Assignee: Orhan Kislal
• Reporter: Frank McQuillan
• Created: 13/Apr/16 23:03
• Updated: 19/Jan/17 21:26
• Resolved: 21/Dec/16 19:11

Description

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)

Issue Links

• is part of: MADLIB-993 Graph (phase 1)
• links to: GitHub Pull Request #78