[Neo4j] allSimplePaths performance

Petar Dobrev peter.dobrev at gmail.com
Thu Nov 24 11:42:33 CET 2011

Hi guys,

I have a graph of about 2.5M nodes and 8M relationships and I am trying to
find all simple paths between two nodes with maximum depth of 8.

The allSimplePaths graph algo works well for maximum depth of 5, but for 8
it runs really long (I didn't even wait for it to finish). So I thought
it's just that the graph is too complicated and the search operation is
very expensive.

On the other hand I noticed that shortestPath and pathsWithLength both work
fast. So I tried this experiment:

   - Run shortestPath and record the shortest length
   - Iterate from the shortest length to max_depth
      - Run pathsWithLength and append the results

And it turns out to be working really well.. much, much faster than the
allSimplePaths solution, which I found quite baffling, since the latter
solution should be doing more work to accomplish the same task.

Maybe it's just with my graph, but it's still weird.

Best regards,

More information about the User mailing list