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

[Manikanta Kondeti]

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>


   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
<https://github.com/manikanta-kondeti/KernelPogramming/tree/master/SharedMemory>

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20150310/2540319d/attachment.html>