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

[Stephen Woodbridge]

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>

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>

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 at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>