Uploaded image for project: 'Apache MADlib'
  1. Apache MADlib
  2. MADLIB-992

Graph - single source shortest path

    XMLWordPrintableJSON

Details

    • New Feature
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • v1.10
    • Module: Graph
    • None

    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)

      Attachments

        1. sssp-grails.sql
          2 kB
          Frank McQuillan
        2. SSSP graph scale tests.pdf
          440 kB
          Frank McQuillan
        3. MADlib_ Single Source Shortest Path.pdf
          127 kB
          Frank McQuillan

        Issue Links

          Activity

            People

              okislal Orhan Kislal
              fmcquillan Frank McQuillan
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: