15
$\begingroup$

I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to have the graph in memory, so the graph is stored on disk in a database.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

Fetching the adjacency list of each vertex visited would require about 1,500 database queries per 10,000 nodes according to my statistical data, so that clearly is not how they do it. That would be way too slow.

How do they do it? I am trying to implement it myself.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ Are you sure they use Dijkstra? There are plenty of other shortest path algorithms that may be better suited to the situation you describe. $\endgroup$
    – David Richerby
    Mar 26 '16 at 16:25
  • 1
    $\begingroup$ Have you looked into the code? How should we know? "database queries" -- I hope you don't use a DBMS for storing graphs? $\endgroup$
    – Raphael ♦
    Mar 26 '16 at 16:39
  • $\begingroup$ @DavidRicherby yes I am sure, look at this link $\endgroup$
    – dimitris93
    Mar 26 '16 at 16:50
  • 2
    $\begingroup$ "[I]t would be an extremely tedious process to look into pure C code." But that's the only way of knowing what the code does. So you're just asking us to do your tedious task for you, which isn't the greatest ad for your question... $\endgroup$
    – David Richerby
    Mar 26 '16 at 18:31
  • 1
    $\begingroup$ @Shiro You explicitly ask, "How do they do this?" If that's not really the question you want to ask, you need to rephrase. $\endgroup$
    – Raphael ♦
    Mar 27 '16 at 7:43
6
$\begingroup$

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

You can use a DB, a custom file format to be read from disc and an in-memory setting.

But from my experience using a DB is roughly 5 to 10 times slower and a lot more memory intense than writing your own file format based on a 'simple' linked list format.

The good thing is there are several software frameworks using OSM which are open source so you can look right into the code e.g. see here. In the GraphHopper open source routing engine it is very easy to switch from a memory mapped setting (disc based) to the in-memory setting - both using the same format. The "mmap" setting even allows usage on memory restricted mobile devices and the latter performs a lot faster if you have the necessary RAM e.g. on a server. E.g. for a world wide graph (>100mio nodes) you then need around 8-10gb RAM, plus lot of more RAM if you want to speed up everything further e.g. with Contraction Hierarchies - roughly 5-8gb more for every vehicle you want.

The format is very simplistic and basically stores only the data you need with a few tricks to make it compact. Read more about it here. Disclaimer: I'm the author of GraphHopper.

Regarding the other answers:

Dijkstras algorithm while applicable is regarded as not optimal for this problem

The 'normal' Dijkstra can perform very reasonable (<1s for country-wide queries like your 3mio nodes example) and is optimal in the 'theory sense' but needs a bit tuning to get fast in production scenarios. And techniques like Contraction Hierachies use a bidirectional modification of it and perform very well.

road networks are hierarchical and planar.

road networks are hierarchical for car only and not planar (bridges, tunnels, ...)

Improve this answer
$\endgroup$
21
  • $\begingroup$ I have one more question. How do you find the NodeID of the closest node from the latitude/longitude ? That is required to calculate shortest path A->B. And also we need to keep in mind that the A and B might not exist as nodes, because not every square meter contains a node. So we need to find the 2 closest NodeIDs of A and B. $\endgroup$
    – dimitris93
    Mar 29 '16 at 17:13
  • $\begingroup$ That is done in the LocationIndexTree which is kind of a quadtree storing efficiently the NodeIDs in a cell which has e.g. for GraphHopper a radius of ~500m. If nothing is found it expands the radius up to a certain degree. This sounds simple in theory but is very complex as you might have edges crossing the area, you need to be efficient when creating and querying it and a lot more. $\endgroup$
    – Karussell
    Apr 1 '16 at 15:50
  • $\begingroup$ Aren't KD-Trees more efficient when searching for the nearest neighbor ? Why did you chose QuadTrees over KD-Trees ? I am implementing KD-Trees for my routing engine right now. I started implementing QuadTrees but I stopped because I figured that KD-Trees is the same thing, but easier to code, and faster to query the nearest neighbor. Am I wrong ? $\endgroup$
    – dimitris93
    Apr 28 '16 at 17:40
  • $\begingroup$ When using quadtrees there is no need to explicitely store the the bounding box giving it a storage advantage, which was more critical for my usecase (also I find quadtrees easier ;)). Query speed is not an issue. In fact someone studied such tries and it outperformed any other implementations incl. KD trees, but I assume all depends on the specific implementation... $\endgroup$
    – Karussell
    Apr 28 '16 at 18:14
  • $\begingroup$ If you look at page 9 of this pdf from stanford, searching for nearest neighbor in KD-Trees doesn't require you to know the bounding boxes at all. And another thing is that because we know all the points beforehand, we can create a balanced tree of logn height. Are still you positive that quadtrees have any advantage over kd-trees ? $\endgroup$
    – dimitris93
    Apr 28 '16 at 20:25
2
$\begingroup$

You do not need to put all edges that are adjacent in the priority queue. "Lie" to Dijkstra's algorithm and give it only the shortest vertex, v, incident to the vertex, say w, pulled off the stack. Then, when v is pulled of the queue you say "oops" I made a mistake and should have given you this vertex too, which is the next closest to vertex w. It is easily seen that this way you will have a correct solution and the queue size is dramatically reduced to one incident vertex only instead of the many. You need though to keep track of the incidences to always give the next closest vertex - when required. One of the comments claimed road networks are planar that is incorrect. In fact, a study has shown they are highly non-planar. Think of all motorways crossing via bridges through a city inducing many non-planarities.

Improve this answer
$\endgroup$
0
$\begingroup$

Dijkstras algorithm while applicable is regarded as not optimal for this problem although more efficient variants could be considered as "similar". there are various simplifications. road networks are hierarchical and planar. here are the basic approaches. the area is generally known as "route planning in road networks".

  • a graph structure can be "compiled" from the adjacency list data. this is the approach in the library you cite, SpatiaLite. these graph structures are stored in a compressed binary format where graph locations are represented by binary-encoded integers etc., so the graph representation and manipulation takes much less space than storing all the road names etc.; it appears the SpatiaLite algorithm is not "online" and runs entirely in memory.

  • there are parallel/ distributed algorithms. see eg Scalable GPU Graph Traversal / Merrill, Garland, Grimshaw.

  • the question uses client-server terminology ie "queries". the algorithms do not run by "querying" the database in the client-server sense. higher level query languages such as SQL are an interface to the database and may be used to transmit the request to compute the minimal routes but are not used by the algorithm internally. generally the algorithm runs "inside the database" ie entirely "server side". so hence writing a shortest path algorithm in database queries is feasible for small networks but not medium/ large scale ones.

  • there is another approach where estimations within small percentages may be acceptable. the basic idea is to keep an index of distances between nodes. see eg Fast and Accurate Estimation of Shortest Paths in Large Graphs / Gubichev, Bedathur, Seufert, Weikum

  • this (235p!) Phd thesis is especially applicable. Route Planning in Road Networks / Schultes

  • some algorithms use many of these ideas and others, are highly tuned and proprietary and verging on competitive trade secrets. eg Google's. there may be some misleading media on this subject. eg The Simple, Elegant Algorithm That Makes Google Maps Possible which claims/ implies Google uses Dijkstras algorithm without any citation.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Google Maps certainly has upgraded to something better than Dijskstra. Every halfway competent developer would use A* for road maps, but at my previous job we found out that Google's engine could replan 2500 km routes via a waypoint in <100 ms. That's too fast for A*, so it's probable they use something like ArcFlags. $\endgroup$
    – MSalters
    Mar 30 '16 at 9:11
  • $\begingroup$ Karussell's answer challenges this opening sentence "Dijkstras algorithm while applicable is regarded as not optimal for this problem" which did not expect would be controversial. there is very strong support for the assertion in the Schultes thesis (early on) which is also a very comprehensive/ recent survey of the area, and also explains the "hierarchical and planar" "approximations". unfortunately there seems to be no indication of the actual google algorithms in open literature on cursory search. $\endgroup$
    – vzn
    Mar 30 '16 at 15:10
-2
$\begingroup$

On extremely large data sets like that, to get such fast results, I find it best to use a union-find data structure with path compression. However, if you are looking to only use Djikstra's algorithm and optimize that, it comes down to what information each node in the graph has. You most likely do not need to do all 1,500 queries.

For instance, consider the following example. Lets say I am trying to find the degrees of separation between any 2 actors (the Bacon number) and I want to find the least weighted path(path using the newest movies possible). Now, let's say I have a function called shortestPath(actor A, actor B);. Consider the following scenario.

If Actor A has been acting since 1970 and Actor B has been acting since 2000, then given that info, it would be much more logical to find a path starting from the first movie of Actor B and then traversing your way to Actor A. As opposed to iterating through every movie Actor A has acted in.

Thus, the main point is that the optimization of Djikstra's algorithm really depends on what your data set is. You would need to provide more information on what your data set entails for us to help you optimize your algorithm.

EDIT: Let's say you are trying to find the shortest path between 2 cities in the same country and if this country is longer than it is wider, for instance, Argentina, then you can do your queries based on the longitude and latitude of the countries boundaries. Then you can start to traverse vertically(using longitude) as opposed to horizontally. Ofc, there would need to be exception handling, but you get the general idea.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How do you use Union-Find in Dijkstra? $\endgroup$
    – Raphael ♦
    Mar 27 '16 at 7:41
  • $\begingroup$ The data are spatial data, latitude and longitude. I thought that was clear. $\endgroup$
    – dimitris93
    Mar 27 '16 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.