[jira] [Created] (TINKERPOP3-737) Bidirectional Traversal Execution

["Matthias Broecheler (JIRA)" <ji...@apache.org>]

Matthias Broecheler created TINKERPOP3-737:
----------------------------------------------

             Summary: Bidirectional Traversal Execution
                 Key: TINKERPOP3-737
                 URL: https://issues.apache.org/jira/browse/TINKERPOP3-737
             Project: TinkerPop 3
          Issue Type: Improvement
            Reporter: Matthias Broecheler


If you have a traversal of the following form inside a MatchStep:
{code}
as('a').out('knows')...[a bunch of steps]..in('bought').as('b')
{code}
where you have bindings for both {{a}} and {{b}}, then the most efficient way to execute the traversal (in most cases) would be bi-directionally, in the sense of bi-directional search [1]. In other words, rather just execute the traversal from {{a}} to the right or inversely from {{b}} to the left, you execute the traversal from both ends and then the result set is the joining of paths that intersect in the middle. The linked Wikipedia article does a good job explaining why this greatly reduces the runtime complexity (and memory complexity).
Now, this only works if the traversal is reversible but a lot of them are.

It would be a great addition if TP3 would be able to execute traversals with end point bindings bi-directionally and for MatchStep/XMatchStep to utilize this feature to greatly improve performance.
Note, that this feature alone would give TP3 a highly performant generic shortest path finder.

[1] https://en.wikipedia.org/wiki/Bidirectional_search



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)