[pgrouting-dev] Reg: Project idea for GSoC'15 (pgRouting)

pgRouting pgrouting-dev
1

Hi all,

My name is Manikanta. I am a dual degree Computer Science student at IIIT-H and pursuing Masters in the field of Spatial Informatics.

I have been an avid user and developer for pgRouting for the past year as my interests lies more on graph theory and routing. I would like to introduce to you this project idea for GSoC 2015, in which I am interested. It might seem a bit large so please bear with me. However, if you are busy and want to read only the title present at the end of the page, please skip the following two points.

The idea of the project can be understood by an amalgamation of the following two phases:

  1. Goal Directed Shortest Path Queries using Precomputed Cluster Distances:

The primarily interesting part in this project is dividing the graph into clusters. Based on the value we select and the cluster size, we can get better results. Like the famous saying,“ It is better to do well than to say well ”, I’ve tried implementing a small sample K-Means clustering. It took a good amount of time to really code this part and this is really interesting and can be optimized further. This is not necessarily specific to K-Means. It could be another Clustering technique as well.

The following link contains the ‘code’, a ‘readme’ file and the corresponding ‘reference paper’.

Link: K-means code

  1. Implementing shared memory object which has the precomputed data:

Usually, when you start an application and it allocates some block of memory, this is freed only after your application terminates. Also, this memory is only accessible to a single process. And then there is shared memory. It allows you to share data among a number of processes and the shared memory we use is persistent. It stays in the system until it is explicitly removed. I’ve tried out an example which creates a shared memory segment and can be accessed via other processes. There is a ‘readme’ file available which explains the basic functionalities of shared memory.

P.S : I haven’t used semaphore in the demo as it takes a huge amount of time.

Link : SharedMemory example code

Basically, the entire idea would be to prepare a pre-computed graph and save the data in a file, then create a process which loads the data into memory and makes it available via shared memory object. I am extremely sure that this project will be very interesting and useful for real world applications.

This is my view on this project and I would be very glad to receive any kind of suggestions or modifications.

Thank you,
Manikanta
MS by Research,
LSI, IIIT-H,
India.

2

On 3/10/2015 2:18 PM, Manikanta Kondeti wrote:

Hi all,

   My name is Manikanta. I am a dual degree Computer Science student at
IIIT-H and pursuing Masters in the field of Spatial Informatics.

   I have been an avid user and developer for pgRouting for the past
year as my interests lies more on graph theory and routing. I would like
to introduce to you this project idea for GSoC 2015, in which I am
interested. It might seem a bit large so please bear with me. However,
if you are busy and want to read only the title present at the end of
the page, please skip the following two points.

The idea of the project can be understood by an amalgamation of the
following two phases:

1.

    Goal Directed Shortest Path Queries using *Precomputed Cluster
    Distances*:

The primarily interesting part in this project is dividing the graph
into clusters. Based on the value we select and the cluster size, we can
get better results. Like the famous saying,“ It is better to do well
than to say well”, I’ve tried implementing a *small sample* K-Means
clustering. It took a good amount of time to really code this part and
this is really interesting and can be optimized further. This is not
necessarily specific to K-Means. It could be another Clustering
technique as well.

The following link contains the ‘code’, a ‘readme’ file and the
corresponding ‘reference paper’.

Link: K-means code
<https://github.com/manikanta-kondeti/codes/tree/master/K-Means&gt;

You might also want to read up on this and ask some question on the dev list:

https://github.com/pgRouting/pgrouting/tree/gsoc-partition/src/partition

This code does partitioning of the graph and dynamic loading of the edges. There is not preprocesssing involved in this code and it ended up not performing all that well. The basic idea was that under normal circumstances, you need to load all edges in a bounding box around your start and end points. If you wanted to route Florida to Alaska it would require loading in all edges in the US. The idea in this project was to load clusters on demand as needed. The performance killer in this was having to repeated go back to the database and import the clusters on demand.

Using shared memory, would make these cluster available much faster.

2.

    Implementing shared memoryobject which has the precomputed data:

Usually, when you start an application and it allocates some block of
memory, this is freed only after your application terminates. Also, this
memory is only accessible to a single process. And then there is shared
memory. It allows you to share data among a number of processes and the
shared memory we use is persistent. It stays in the system until it is
explicitly removed. I’ve tried out an example which creates a shared
memory segment and can be accessed via other processes. There is a
‘readme’ file available which explains the basic functionalities of
shared memory.

P.S : I haven’t used semaphore in the demo as it takes a huge amount of
time.

Link : SharedMemory example code
<https://github.com/manikanta-kondeti/KernelPogramming/tree/master/SharedMemory&gt;

This is a great start, to work out the infrastructure pieces. This gives you a good starting point for developing the rest of the code.

Do you have any ideas on how hard it will be to preprocess the data and to implement the routing part of the code.

Thanks,
   -Steve

Basically, the entire idea would be to prepare a pre-computed graph and
save the data in a file, then create a process which loads the data into
memory and makes it available via shared memory object. I am extremely
sure that this project will be very interesting and useful for real
world applications.

This is my view on this project and I would be very glad to receive any
kind of suggestions or modifications.

Thank you,
Manikanta
MS by Research,
LSI, IIIT-H,
India.

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev