lucene-dev mailing list archives

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

    [ https://issues.apache.org/jira/browse/SOLR-8888?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15216080#comment-15216080
] 

Joel Bernstein edited comment on SOLR-8888 at 3/29/16 2:35 PM:
---------------------------------------------------------------

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 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
well. 


was (Author: joel.bernstein):
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
well. 

> Add shortestPath Streaming Expression
> -------------------------------------
>
>                 Key: SOLR-8888
>                 URL: https://issues.apache.org/jira/browse/SOLR-8888
>             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.
> 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* *joining* 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
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message