I got a chat from Mukul who was a past GSoC student and he says:
"I have been working on a contraction based approach for path computation where we are trying to observe the trade off between different level of network contraction and final unpacking of the path computed on these contracted networks. I have been doing this in my free time for now with one of my junior, Rohit Reddy. The contraction does make the path computation faster and we have implemented all these functionality (precomputation and routing) as database procedure which can be integrated very easily in pgrouting . As soon as we are ready with a tried and tested procedure , i will let you know . You can review it then."
They think they might have something to review in a few weeks that we can take a look at.
This is a very exciting and surprising development!
It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
site's "References" section,
so I think that it will be a quite nice improvement for pgRouting.
Regards,
Ko
2015-12-23 0:00 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
Hi All,
I got a chat from Mukul who was a past GSoC student and he says:
"I have been working on a contraction based approach for path computation
where we are trying to observe the trade off between different level of
network contraction and final unpacking of the path computed on these
contracted networks. I have been doing this in my free time for now with one
of my junior, Rohit Reddy. The contraction does make the path computation
faster and we have implemented all these functionality (precomputation and
routing) as database procedure which can be integrated very easily in
pgrouting . As soon as we are ready with a tried and tested procedure , i
will let you know . You can review it then."
They think they might have something to review in a few weeks that we can
take a look at.
This is a very exciting and surprising development!
I believe that is correct, but I have not seem the actual code Mukul and Rohit are developing. I'm also not sure how the precomputed graph is getting stored/retrieved which will directly impact the compute time.
In pgRouting today, I think we spend our compute time roughly like:
1/3 - fetching edges
1/3 - building the graph
1/3 - computing results
Depending on the exact implementation this should eliminate much building the graph and computing results. And instead of fetching edges we would be fetching the contracted graph.
Also, this technique trades off dynamic graph definition for performance because you have to precompute the contracted graph which is time consuming and only has value if you want to build once and solve many times. If you want to change the weights or add or remove edges, then you have to precompute the contracted graph again.
Regardless of the details, this will be a very nice addition to pgRouting.
-Steve
On 12/23/2015 8:36 AM, Ko Nagase wrote:
Hi Stephen, Mukul,
Thanks for good news!
Does "contraction hierarchies" mean the following technique ?
It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
site's "References" section,
so I think that it will be a quite nice improvement for pgRouting.
Regards,
Ko
2015-12-23 0:00 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
Hi All,
I got a chat from Mukul who was a past GSoC student and he says:
"I have been working on a contraction based approach for path computation
where we are trying to observe the trade off between different level of
network contraction and final unpacking of the path computed on these
contracted networks. I have been doing this in my free time for now with one
of my junior, Rohit Reddy. The contraction does make the path computation
faster and we have implemented all these functionality (precomputation and
routing) as database procedure which can be integrated very easily in
pgrouting . As soon as we are ready with a tried and tested procedure , i
will let you know . You can review it then."
They think they might have something to review in a few weeks that we can
take a look at.
This is a very exciting and surprising development!
About a huge network, I think that the performance is the highest priority
and dynamic graph (CRUD and dynamic condition) is not so important.
But, if possible, supporting multiple weights (like bicycle and car
.etc) may be good.
(In FOSS4G 2015 Seoul, I heard that OSRM requires multiple instances (daemons)
for multiple profiles and it is a bit complex.)
Anyway, I'm looking forward to it.
Regards,
Ko
2015-12-23 23:20 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
I believe that is correct, but I have not seem the actual code Mukul and
Rohit are developing. I'm also not sure how the precomputed graph is getting
stored/retrieved which will directly impact the compute time.
In pgRouting today, I think we spend our compute time roughly like:
1/3 - fetching edges
1/3 - building the graph
1/3 - computing results
Depending on the exact implementation this should eliminate much building
the graph and computing results. And instead of fetching edges we would be
fetching the contracted graph.
Also, this technique trades off dynamic graph definition for performance
because you have to precompute the contracted graph which is time consuming
and only has value if you want to build once and solve many times. If you
want to change the weights or add or remove edges, then you have to
precompute the contracted graph again.
Regardless of the details, this will be a very nice addition to pgRouting.
-Steve
On 12/23/2015 8:36 AM, Ko Nagase wrote:
Hi Stephen, Mukul,
Thanks for good news!
Does "contraction hierarchies" mean the following technique ?
It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
site's "References" section,
so I think that it will be a quite nice improvement for pgRouting.
Regards,
Ko
2015-12-23 0:00 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
Hi All,
I got a chat from Mukul who was a past GSoC student and he says:
"I have been working on a contraction based approach for path computation
where we are trying to observe the trade off between different level of
network contraction and final unpacking of the path computed on these
contracted networks. I have been doing this in my free time for now with
one
of my junior, Rohit Reddy. The contraction does make the path computation
faster and we have implemented all these functionality (precomputation
and
routing) as database procedure which can be integrated very easily in
pgrouting . As soon as we are ready with a tried and tested procedure ,
i
will let you know . You can review it then."
They think they might have something to review in a few weeks that we can
take a look at.
This is a very exciting and surprising development!
We will have to see the details in a few weeks as I have no more information that what Mukul chatted and the rest is speculation on my part. If the contracted graph is stored in a table or even a named file, then it should be possible to store multiple profiles and then select which profile to use in a specific query.
I would think that even if it is not implemented like that on the initial preview that we should be able to grow it to support something like that.
-Steve
On 12/23/2015 10:59 AM, Ko Nagase wrote:
Hi Stephen,
Thanks for details.
About a huge network, I think that the performance is the highest priority
and dynamic graph (CRUD and dynamic condition) is not so important.
But, if possible, supporting multiple weights (like bicycle and car
.etc) may be good.
(In FOSS4G 2015 Seoul, I heard that OSRM requires multiple instances (daemons)
for multiple profiles and it is a bit complex.)
Anyway, I'm looking forward to it.
Regards,
Ko
2015-12-23 23:20 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
I believe that is correct, but I have not seem the actual code Mukul and
Rohit are developing. I'm also not sure how the precomputed graph is getting
stored/retrieved which will directly impact the compute time.
In pgRouting today, I think we spend our compute time roughly like:
1/3 - fetching edges
1/3 - building the graph
1/3 - computing results
Depending on the exact implementation this should eliminate much building
the graph and computing results. And instead of fetching edges we would be
fetching the contracted graph.
Also, this technique trades off dynamic graph definition for performance
because you have to precompute the contracted graph which is time consuming
and only has value if you want to build once and solve many times. If you
want to change the weights or add or remove edges, then you have to
precompute the contracted graph again.
Regardless of the details, this will be a very nice addition to pgRouting.
-Steve
On 12/23/2015 8:36 AM, Ko Nagase wrote:
Hi Stephen, Mukul,
Thanks for good news!
Does "contraction hierarchies" mean the following technique ?
It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
site's "References" section,
so I think that it will be a quite nice improvement for pgRouting.
Regards,
Ko
2015-12-23 0:00 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
Hi All,
I got a chat from Mukul who was a past GSoC student and he says:
"I have been working on a contraction based approach for path computation
where we are trying to observe the trade off between different level of
network contraction and final unpacking of the path computed on these
contracted networks. I have been doing this in my free time for now with
one
of my junior, Rohit Reddy. The contraction does make the path computation
faster and we have implemented all these functionality (precomputation
and
routing) as database procedure which can be integrated very easily in
pgrouting . As soon as we are ready with a tried and tested procedure ,
i
will let you know . You can review it then."
They think they might have something to review in a few weeks that we can
take a look at.
This is a very exciting and surprising development!
Yes we are basically introducing shortcuts what contraction hierarchy does right now.This pre-computation will be done by a database procedure which will be a user defined function. The amount of shortcuts introduced determines the level of contraction. However there is a trade off between the amount of contraction and the time taken to unpack the path computed on the contracted network.
So there will be a precomputaion involved in which we will populate a table containing the contracted network, this table with the contracted graph will be fetched for path computation .
The difference between Contraction hierarchy and our approach is that in CH , there is a hierarchy of nodes maintained and there path computation algorithm has an upward Graph and a downward graph and they process the nodes from the both the directions using the hierarchy of the nodes .
I believe that is correct, but I have not seem the actual code Mukul and
Rohit are developing. I’m also not sure how the precomputed graph is getting
stored/retrieved which will directly impact the compute time.
In pgRouting today, I think we spend our compute time roughly like:
1/3 - fetching edges
1/3 - building the graph
1/3 - computing results
Depending on the exact implementation this should eliminate much building
the graph and computing results. And instead of fetching edges we would be
fetching the contracted graph.
Also, this technique trades off dynamic graph definition for performance
because you have to precompute the contracted graph which is time consuming
and only has value if you want to build once and solve many times. If you
want to change the weights or add or remove edges, then you have to
precompute the contracted graph again.
Regardless of the details, this will be a very nice addition to pgRouting.
-Steve
On 12/23/2015 8:36 AM, Ko Nagase wrote:
Hi Stephen, Mukul,
Thanks for good news!
Does “contraction hierarchies” mean the following technique ?
It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
site’s “References” section,
so I think that it will be a quite nice improvement for pgRouting.
I got a chat from Mukul who was a past GSoC student and he says:
“I have been working on a contraction based approach for path computation
where we are trying to observe the trade off between different level of
network contraction and final unpacking of the path computed on these
contracted networks. I have been doing this in my free time for now with
one
of my junior, Rohit Reddy. The contraction does make the path computation
faster and we have implemented all these functionality (precomputation
and
routing) as database procedure which can be integrated very easily in
pgrouting . As soon as we are ready with a tried and tested procedure ,
i
will let you know . You can review it then.”
They think they might have something to review in a few weeks that we can
take a look at.
This is a very exciting and surprising development!
Steve is right here about the trade off with dynamic nature of the graph . It is kind of difficult to update the edge weights in contracted graph. One has to do the pre computation once again and generate the contracted graph.This technique will be helpful to people who want to run querries on the same static network.
Yes we are basically introducing shortcuts what contraction hierarchy does right now.This pre-computation will be done by a database procedure which will be a user defined function. The amount of shortcuts introduced determines the level of contraction. However there is a trade off between the amount of contraction and the time taken to unpack the path computed on the contracted network.
So there will be a precomputaion involved in which we will populate a table containing the contracted network, this table with the contracted graph will be fetched for path computation .
The difference between Contraction hierarchy and our approach is that in CH , there is a hierarchy of nodes maintained and there path computation algorithm has an upward Graph and a downward graph and they process the nodes from the both the directions using the hierarchy of the nodes .
I believe that is correct, but I have not seem the actual code Mukul and
Rohit are developing. I’m also not sure how the precomputed graph is getting
stored/retrieved which will directly impact the compute time.
In pgRouting today, I think we spend our compute time roughly like:
1/3 - fetching edges
1/3 - building the graph
1/3 - computing results
Depending on the exact implementation this should eliminate much building
the graph and computing results. And instead of fetching edges we would be
fetching the contracted graph.
Also, this technique trades off dynamic graph definition for performance
because you have to precompute the contracted graph which is time consuming
and only has value if you want to build once and solve many times. If you
want to change the weights or add or remove edges, then you have to
precompute the contracted graph again.
Regardless of the details, this will be a very nice addition to pgRouting.
-Steve
On 12/23/2015 8:36 AM, Ko Nagase wrote:
Hi Stephen, Mukul,
Thanks for good news!
Does “contraction hierarchies” mean the following technique ?
It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
site’s “References” section,
so I think that it will be a quite nice improvement for pgRouting.
I got a chat from Mukul who was a past GSoC student and he says:
“I have been working on a contraction based approach for path computation
where we are trying to observe the trade off between different level of
network contraction and final unpacking of the path computed on these
contracted networks. I have been doing this in my free time for now with
one
of my junior, Rohit Reddy. The contraction does make the path computation
faster and we have implemented all these functionality (precomputation
and
routing) as database procedure which can be integrated very easily in
pgrouting . As soon as we are ready with a tried and tested procedure ,
i
will let you know . You can review it then.”
They think they might have something to review in a few weeks that we can
take a look at.
This is a very exciting and surprising development!
Steve is right here about the trade off with dynamic nature of the graph .
It is kind of difficult to update the edge weights in contracted graph. One
has to do the pre computation once again and generate the contracted
graph.This technique will be helpful to people who want to run querries on
the same static network.
-mukul
On Wed, Dec 23, 2015 at 10:43 PM, Mukul priya <mukul2047@gmail.com> wrote:
Hi ,
Yes we are basically introducing shortcuts what contraction hierarchy does
right now.This pre-computation will be done by a database procedure which
will be a user defined function. The amount of shortcuts introduced
determines the level of contraction. However there is a trade off between
the amount of contraction and the time taken to unpack the path computed on
the contracted network.
So there will be a precomputaion involved in which we will populate a
table containing the contracted network, this table with the contracted
graph will be fetched for path computation .
The difference between Contraction hierarchy and our approach is that in
CH , there is a hierarchy of nodes maintained and there path computation
algorithm has an upward Graph and a downward graph and they process the
nodes from the both the directions using the hierarchy of the nodes .
Thanks
Mukul
On Wed, Dec 23, 2015 at 9:29 PM, Ko Nagase <nagase@georepublic.co.jp>
wrote:
Hi Stephen,
Thanks for details.
About a huge network, I think that the performance is the highest
priority
and dynamic graph (CRUD and dynamic condition) is not so important.
But, if possible, supporting multiple weights (like bicycle and car
.etc) may be good.
(In FOSS4G 2015 Seoul, I heard that OSRM requires multiple instances
(daemons)
for multiple profiles and it is a bit complex.)
Anyway, I'm looking forward to it.
Regards,
Ko
2015-12-23 23:20 GMT+09:00 Stephen Woodbridge <woodbri@swoodbridge.com>:
> I believe that is correct, but I have not seem the actual code Mukul
> and
> Rohit are developing. I'm also not sure how the precomputed graph is
> getting
> stored/retrieved which will directly impact the compute time.
>
> In pgRouting today, I think we spend our compute time roughly like:
>
> 1/3 - fetching edges
> 1/3 - building the graph
> 1/3 - computing results
>
> Depending on the exact implementation this should eliminate much
> building
> the graph and computing results. And instead of fetching edges we would
> be
> fetching the contracted graph.
>
> Also, this technique trades off dynamic graph definition for
> performance
> because you have to precompute the contracted graph which is time
> consuming
> and only has value if you want to build once and solve many times. If
> you
> want to change the weights or add or remove edges, then you have to
> precompute the contracted graph again.
>
> Regardless of the details, this will be a very nice addition to
> pgRouting.
>
> -Steve
>
>
> On 12/23/2015 8:36 AM, Ko Nagase wrote:
>>
>> Hi Stephen, Mukul,
>>
>> Thanks for good news!
>>
>> Does "contraction hierarchies" mean the following technique ?
>> ===
>> [Contraction hierarchies - Wikipedia, the free encyclopedia]
>> Contraction hierarchies - Wikipedia
>> ===
>>
>> It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
>> site's "References" section,
>> so I think that it will be a quite nice improvement for pgRouting.
>>
>> Regards,
>>
>> Ko
>>
>> 2015-12-23 0:00 GMT+09:00 Stephen Woodbridge
>> <woodbri@swoodbridge.com>:
>>>
>>> Hi All,
>>>
>>> I got a chat from Mukul who was a past GSoC student and he says:
>>>
>>> "I have been working on a contraction based approach for path
>>> computation
>>> where we are trying to observe the trade off between different level
>>> of
>>> network contraction and final unpacking of the path computed on these
>>> contracted networks. I have been doing this in my free time for now
>>> with
>>> one
>>> of my junior, Rohit Reddy. The contraction does make the path
>>> computation
>>> faster and we have implemented all these functionality
>>> (precomputation
>>> and
>>> routing) as database procedure which can be integrated very easily in
>>> pgrouting . As soon as we are ready with a tried and tested
>>> procedure ,
>>> i
>>> will let you know . You can review it then."
>>>
>>> They think they might have something to review in a few weeks that we
>>> can
>>> take a look at.
>>>
>>> This is a very exciting and surprising development!
>>>
>>> -Steve
>>>
>>> ---
>>> This email has been checked for viruses by Avast antivirus software.
>>> Download Free Antivirus Software | Avast 2024 PC Protection
>>>
>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev@lists.osgeo.org
>>> pgrouting-dev Info Page
>>
>>
>>
>>
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> Download Free Antivirus Software | Avast 2024 PC Protection
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev@lists.osgeo.org
> pgrouting-dev Info Page
--
Ko Nagase (長瀬 興)
Georepublic Japan
mail: nagase@georepublic.co.jp
web: http://georepublic.co.jp
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org pgrouting-dev Info Page
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org pgrouting-dev Info Page
--
Ko Nagase (長瀬 興)
Georepublic Japan
mail: nagase@georepublic.co.jp
web: http://georepublic.co.jp
