Uploaded image for project: 'Solr'
  1. Solr
  2. SOLR-8888

Add shortestPath Streaming Expression

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Implemented
    • Affects Version/s: 6.1
    • Fix Version/s: 6.1
    • Component/s: None
    • Labels:
      None

      Description

      This ticket is to implement a distributed shortest path graph traversal as a Streaming Expression.

      Expression syntax:

      shortestPath(collection, 
                           from="john@company.com", 
                           to="jane@company.com",
                           edge="from=to",
                           threads="6",
                           partitionSize="300", 
                           fq="limiting query", 
                           maxDepth="4")
      

      The expression above performs a breadth first search to find the shortest paths in an unweighted, directed graph. The search starts from the node john@company.com and searches for the node jane@company.com, traversing the edges by iteratively joining the from and to columns. Each level in the traversal is implemented as a parallel partitioned nested loop join across the entire collection. The threads parameter controls the number of threads performing the join at each level. The partitionSize controls the of number of nodes in each join partition. maxDepth controls the number of levels to traverse. fq is a limiting query applied to each level in the traversal.

      Future implementations can add more capabilities such as weighted traversals.

        Attachments

        1. SOLR-8888.patch
          10 kB
          Joel Bernstein
        2. SOLR-8888.patch
          22 kB
          Joel Bernstein
        3. SOLR-8888.patch
          22 kB
          Joel Bernstein
        4. SOLR-8888.patch
          22 kB
          Joel Bernstein
        5. SOLR-8888.patch
          43 kB
          Joel Bernstein
        6. SOLR-8888.patch
          43 kB
          Joel Bernstein
        7. SOLR-8888.patch
          45 kB
          Joel Bernstein
        8. SOLR-8888.patch
          42 kB
          Joel Bernstein
        9. SOLR-8888.patch
          42 kB
          Joel Bernstein
        10. SOLR-8888.1.patch
          8 kB
          Cao Manh Dat

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                joel.bernstein Joel Bernstein
              • Votes:
                0 Vote for this issue
                Watchers:
                5 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: