externalize routing functions?
Status: Pre-Alpha
Brought to you by:
sakaal
Menu
▾
▴
Though I'm able to do a native build of the pgrouting lib on XP, during calls to shortest_path_shooting_star it bombs somewhere in the boost/graph templates. I had hopes that a native build would allow me to look closer at the reverse_cost/one-way routing problem previously discussed.
I'd be curious to hear your thoughts about externalizing the query functions from postgresql, instead of using stored functions to do the job. Do you think much performance would be lost in going through the external query interface to retrieve and create edge graph, run the query, etc vs using the PostGreSQL SPI api to call pgrouting?
I'm afraid I can't really answer the question with performance comparison. However, I have thought about experimenting with some routing algorithms on my own in the way you described. In other words: writing the routing algorithm outside PostgreSQL. I would do it in Java because that has been my main language for some years now. In any case, the performance depends heavily on how the graph is built. Using a bounding box to fetch the whole area might be very ineffective, especially for longer routes. Fetching little by little as the search propagates would mean a lot of small queries. Or perhaps, we could try a tiled approach that would first fetch smaller boxes ('tiles') around the source and the destination, and then spread to adjacent tiles whenever the search hits the bounds of the current graph. That combined with some clever variation of bidirectional Dijkstra, perhaps with a dash of geographical location-aware heuristics, and a properly synchronized multithreading design… I believe that could do the trick.
Looking through pgrouting it appears a full graph is constructed for each shortest_path_shooting_star query, which probably explains the near constant time regardless of nodes or edges traversed. Thanks for the insight.
Testing with modified pgrouting code which is external to the server (and using the sql front end, vice PostGreSQL SPI) shows that a shortest_path_shooting_star query that takes in 5 seconds internally takes about 45-50 secs externally. Quite a delta.