lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Joel Bernstein (JIRA)" <>
Subject [jira] [Commented] (SOLR-8888) Add shortestPath Streaming Expression
Date Tue, 29 Mar 2016 14:24:25 GMT


Joel Bernstein commented on SOLR-8888:

I think we can approach graph work in much the same way we approached relational algebra.
We have some specific streams that do joins etc... and we have a ReducerStream which could
can do lot's of relational algebra on it's own. Eventually the ReducerStream could power some
of the joins like it currently powers unique.

With graph queries we can have some specific expressions and a generic reduce expression as

> Add shortestPath Streaming Expression
> -------------------------------------
>                 Key: SOLR-8888
>                 URL:
>             Project: Solr
>          Issue Type: Improvement
>            Reporter: Joel Bernstein
>         Attachments: SOLR-8888.patch, SOLR-8888.patch, SOLR-8888.patch, SOLR-8888.patch
> This ticket is to implement a distributed shortest path graph traversal as a Streaming
> Expression syntax:
> {code}
> shortestPath(collection, 
>                      from="node1", 
>                      to="node2",
>                      edge="colA, colB",
>                      threads="6",
>                      partitionSize="300", 
>                      fq="limiting query", 
>                      maxDepth="4")
> {code}
> Th expression above performs a *breadth first search* to find the shortest path in an
unweighted, directed graph. The search is performed  *from* node1 *to* node2, traversing the
*edge* columns colA to colB iteratively. Each level in the traversal is implemented as a *parallel
partitioned* nested loop join. 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.

This message was sent by Atlassian JIRA

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message