a simple query getting stuck

1
votes

I have a neo4j database with 3~ million nodes and approx 9 million relationships between them. I'm trying to find shortest paths between two given nodes, which can go both ways (relationship directions are not important), with the following query:

START a=node:CONTACTS(number='3742') , b=node:CONTACTS(number='7423')
MATCH p=a-[r*..5]-b
WITH p, relationships(p) as rcoll
RETURN p, REDUCE(totalTime=0, x in rcoll | totalTime + x.time) as totalTime
ORDER BY totalTime ASC
LIMIT 5;

but this query gets stuck and never return a result. any idea why or how to debug this?

thanks,

2
neo4jcyphergraph-databases
You might be traversing r relationships several times, or? What prevents this from happening? – fbiville
what should I do to prevent this? – Ronen Ness

2 Answers

2
votes

You could also use the path-finding REST-API, where you provide the start and end-nodes, the types of relationships to traverse and you can provide a cost variable or a function to compute.

See: http://neo4j.com/docs/stable/rest-api-graph-algos.html

Example request

POST http://localhost:7474/db/data/node/54/path
{
  "to" : "http://localhost:7474/db/data/node/51",
  "cost_property" : "time",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

if you want to combine that with your index lookup you might want to use the REST-BATCH-API and replace the node-urls with {1} and {2} for the batch-id's respectively.

http://neo4j.com/docs/stable/rest-api-batch-ops.html#rest-api-refer-to-items-created-earlier-in-the-same-batch-job

1
votes

For weighted shortest paths in a relatively big dataset, you really need to use the graphalgo package in Java, and build an unmanaged extension (if you're using Neo4j server). Cypher's reduce isn't optimized for this sort of query. Weighted shortest paths will probably have syntax in Cypher eventually.

This should get you started: http://neo4j.com/docs/stable/tutorials-java-embedded-graph-algo.html