[pgrouting-dev] memory usage in bulk routing

[Alec Gosse]

Steve,

I'm using a large number of routes to compute the likelihood that a vehicle (bicycle) observed at one edge would use other edges on the same trip as means of spatial extrapolation for limited vehicle count data. I wondered about the overhead of creating the graph.  Building a single graph definitely sounds preferable for my application. I'm using A* since shooting star seems to be missing from the dev install, but I would prefer to route from edge to edge rather than using vertices.   

My goal is to write a table of edges traversed, in order, from an input table of start and destination edges. I believe that this is your second suggested use case. I'm game to code this with some guidance on where to start. Ideally, the function would build a graph and then do the routing on multiple threads reading the one graph. I know how to use openMP for this part, but am I correct that pgRouting is using boost threads?

Best,
Alec


On May 10, 2013, at 1:20 PM, Stephen Woodbridge <woodbri at swoodbridge.com> wrote:

> On 5/10/2013 12:34 PM, Alec Gosse wrote:
>> Hello, and please let me know if this off topic for this list.
>> 
>> My application processes a large number of routes (~500k) in a batch.
>> Each routing task is independent, however even processing ~100
>> requires multiple GB of ram on a graph of 50k edges. Memory usage
>> grows continually as the query is running rather than leveling out as
>> I would expect, which makes me think that each routing task is
>> holding onto its memory until they all finish. I tried breaking the
>> query into small chunks within a plpgsql loop, but to no benefit.
>> 
>> Is this an accurate assessment, and or, is there a feasible way to
>> route many trips in bulk from a table of start and end points?
> 
> Alec,
> 
> What routing algorithm (function) are you using?
> This sounds like there might be a memory leak. The other possibility is that this is all getting done in a single transaction and I have run into issues because of this. For example, I had a process that I wrapped into a stored procedure to iterate through a table, run a query and update a table and that soaked up huge amounts of memory, but when I rewrote it in perl as a client side script that did a query of a table and then issued a new queries for each table row it did not use a lot of memory. My understanding is that everything done in a stored procedure is done implicitly in a transaction. So the perl script was done in a transaction.
> 
> If you are interested in coding some C/C++, one idea that I had is to create a function that takes a list of locations, builds a single graph then computes the distances for all pair combinations in the list. Another variant of this would be to pass it a list of location pairs, and it could return a tout for each pair.
> 
> A large part of the cost is in building the graph, so if you can do it once and reuse it, then you get a huge benefit. I have not had time of funding to build something like this but it would be a great feautre to add to pgrouting. What is your use case for?
> 
> -Steve
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev