Slow neo4j Cypher Queries, using Baconator query for less-short paths than shortest path

Question

I have an indexed neo4j DB with 200,000 nodes and close to 4 million relationships (two types of relationships). Using the C# API, I am trying to do a "Baconator" type of query that not only gives me the shortest path, but gives me the some of the other shorter paths. (E.g. If the shortest path has 3 nodes, I would also like to see the other runner-up results of length 4, 5.. ect.).

This is the query I use first (in C# call):

string whereClause = "a.Id='" + userId.ToUpper() + "' and b.Id='" + targetId.ToUpper() + "'";

            var query = graphClient.Cypher
                .Match("p=allShortestPaths((a:Person)-[*..6]-(b:Person))")
                .Where(whereClause)
                .ReturnDistinct<List<Person>>("nodes(p)").Limit(5);

This only gives me the paths of the shortest length. To get the other less-short paths, I am using the following:

//nextDegree starts at the degree of the shortest path
while (nextDegree <= 6)
{
    var auxiliaryQuery = graphClient.Cypher
                    .Match("p=(a:Person)-[*" + (nextDegree) + ".." + (nextDegree) + "]-(b:Person)")
                    .Where(whereClause)
                    .ReturnDistinct<List<Person>>("nodes(p)").Limit(limit);
}

This works, but performance takes quite a hit, as queries take over 30 seconds when reaching length of 5, and minutes when reaching 6.

My question is: Is there a way I can optimize this? (Either by using the simple path algorithm within Cypher or other methods)

Michal Bachman Michal Bachman · Accepted Answer · 2014-08-13T20:36:43

Have a look at this plugin to the GraphAware Framework which has been written precisely for this use case. It finds increasingly longer shortest paths. It hasn't been properly released yet, but it's ready to go and fully tested, you'll just have to build it yourself (get in touch if you need help).

Once built, it's a matter of dropping jar files into the plugins directory and calling a REST API.

Slow neo4j Cypher Queries, using Baconator query for less-short paths than shortest path

1 Answers