<p>The breakthrough with graph databases is not only performances, it more about concept: your routing algorithms deal with <strong>single relational graphs</strong> (that is graph were links are all of the same type) whereas with graphdatabases you have a <strong>multi-relational graph</strong>.</p>

<p>This enables you to compute the shortest path between nodes taking only a specific kind of edge or avoid another type.</p>

<p>For more information you should read about <a href="http://arxiv.org/abs/0806.2274" rel="nofollow">the algebra behind graph db</a> and the concept of pipes.</p>

<p>I strongly recommend <a href="http://www.tinkerpop.com/" rel="nofollow">thinkerpop</a> project to start with graph database.</p>
Is a graph database better for shortest paths algorithms?
<p>My objective is to write a shortest path algorithm for a road network.</p>

<p>Currently my architecture is something like that: I store all the data in the PostGIS enabled PostgreSQL database. I do one <code>SELECT * FROM ways</code>, which takes less than 3 seconds on a table with 100,000 edges (ways) and after that I will apply a (Java, Ruby or anything-based) shortest path algorithm to the graph that already resides in memory. The second operation can take about 1.5 seconds on a graph with 100,000 edges. </p>

<p>So, it takes:</p>

<ul>
<li>2-3 seconds to load all the ways from the database into memory and create a graph (nodes are stored in one table with ways(edges));</li>
<li>1-1.5 seconds to calculate a shortest path on a graph which is already in memory.</li>
</ul>

<p>This is very similar to what pgRouting does (to my knowledge it uses C Boost to store the graph in memory), except pgRouting takes about 2 seconds in total to compute a shortest path on the same data set (yes, it is fast, but it is a black box for me, so I need my own).</p>

<p>But recently I found about Graph databases and about Neo4j. On their site they claim that "Still being able to do these calculations in sub-second speeds on graphs of millions of roads and waypoints makes it possible in many cases to abandon the normal approach of precomputing indexes with K/V stores and be able to put routing into the critical path with the possibility to adapt to the live conditions and build highly personalized and dynamic spatial services.".</p>

<p>So the question is: Will a graph database be faster with my particular problem?</p>

<p>The problem has the following properties:</p>

<ul>
<li>the database consists of one table (ways);</li>
<li>the only query to the database is to get all the ways into the memory (to build a graph);</li>
<li>I do not need scalability, i.e. it is likely that the graph will not grow.</li>
</ul>