How to handle updates to pgRouting network in webmapping environment?

Question

I'm building an application for a client of mine that will need to create routes in a PostgreSQL database.

So far so good, but I need to support edits and changes to my network and I need to support bulk imports.

I've read the tutorials and the examples available on the web and the routing part is clear for me.

My main concern is perfomance. If I try to update the network at each update, this will be incredibly slow. Here's the workflow I'm thinking for creating new edges:

1. User inserts a new edge (let's call that A);
2. System looks for existing edges that touches or crosses this new edge (edge B);

3. System splits edge B (if touches) and/or splits edge A (if crosses);

   This will trigger another event at the database (recalculating the new nodes for each of B splitted parts B and B');

4. System looks for existing nodes for edge A;

5. If nodes found, update the feature to maintain the network topology (from to node ids);
6. If no nodes are found, create them and update the necessary features;

Of course there will be similar triggers for updates to the edges (this may be even more complex than the above) and deletes. For a small number of users it may be acceptable, but for bulk imports this is unlikely to work (I have three of four spatial queries being run for each update).

My bulk process will be run using async tasks (Celery). As whuber always says, if it's too slow, blaim the algorithm.

I have a similar setup with ESRI software for a customized network scheme and works well, but it's not the fastest kid on the block.

I have two ways of doing this: in the application layer or in the database. The database is a good choice IMO but I may leak the domain layer to the database and I REALLY don't want to do that. The application is being developed with GeoDjango.

What are your thoughts on this?

Can you guys comment on the algorithm?

This is a more django-specific question: can I query memcached entities using spatial queries?

Answer 1

Just look for new seg ids, merge new segs. update the database, update the application layer from the database, rerun the routing application, update the routing. Why only break one edge for join as both edges would break if there is a new seg id. segments aren't edges but edge pairs and end nodes pairs.

Answer 2

After two years, I'm here to tell you how I did it. It may not be perfect, but it's something.

Our cartographic production is limited to some counties inside Brazil. We never update just some part of the graph, but whole cities. So, whenever a city has major cartographic changes, everything is destroyed and replaced.

About planarizing the graphs, this is done in the GIS environment. The node construction happens after upload. It takes about 3-5 minutes to update a big city with ~100.000 nodes (this was moved directly to the database).

This all or none approach works fairly well, since our updates to the graph are not that common and not that rare (a city will get an update every month, at most).