[pgrouting-dev] K-Shortest Paths performance issues

[Stephen Woodbridge]

On 1/23/2014 5:34 PM, Paulo Figueiras wrote:
> Hi, Steve.
>
> Thanks for your fast response.
>
>
>     The seems a little excessive to me, but I have not used it enough to
>     have any idea what to expect.
>
>
> So it seems :) I'm running pgrouting on a Ubuntu virtual machine with 2
> cores and 4GB of RAM.
>
>     Can you run ksp with k=1? or does it automatically adjust it upward
>     to k=2?
>
> I can try to run with k=1, although I use Dijkstra or A* for single
> routes. I would really like to use KSP for 2 to 5 route options.

Right, but this will indicate if the problem is with the basic algorithm 
implementation, ie: k=1 should be able the same as Dijkstra, or if the 
problem is extracting the additional routes.

Another test would be time k=1, k=2, k=3, k=4, k=5 using the same input 
parameters, so we can see how the graphs out.

>     Does this happen for ALL cases? or only sometimes?
>
> I tried a few times and it is consistent.
>
>
>     Can you make a small graph test case the shows this behavior? The
>     can be used to debugging the problem.
>
> What I'll do is I'll migrate my code to a more powerful server this
> weekend, and I'll test KSP with k=2 there to check for improvements. In
> the meantime, I'll try k=1 in the virtual machine.
>
> I'll report results next week. Again, thank you very much.

Ok, cool. My experience with VMs is that they tend to have performance 
issues, but it not a large sample. Anyway, Look forward to any addition 
results you can generate.

Thanks,
   -Steve

> Best,
>
> --
>
> Paulo Figueiras <paf at uninova.pt <mailto:%3Crddc at uninova.pt>>____
>
> cid:image002.jpg at 01C8AEC7.2F6E45A0 <http://www.uninova.pt/>____
>
> __ __
>
> 	
>
> UNINOVA, Centre of Technology and Systems
> Campus da Caparica, Quinta da Torre
> 2829-516 Monte Caparica, PORTUGAL____
>
> Phone: (+351) 212948312 | Fax: (+351) 212957786 | Website:
> http://www.uninova.pt/
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>