<div dir="ltr"><span id="docs-internal-guid-02ff2700-04e5-1c60-a763-d52586e1f247"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Hi all, </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">   My name is Manikanta. I am a dual degree Computer Science student at IIIT-H and pursuing Masters in the field of Spatial Informatics.  </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">   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. </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The idea of the project can be understood by an amalgamation of the following two phases: </span></p><br><ol style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Goal Directed Shortest Path Queries using <b>Precomputed Cluster Distances</b>:</span></p></li></ol><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><span class="" style="white-space:pre">      </span></span><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><span class="" style="white-space:pre">   </span></span><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">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,“ </span><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap">It is better to do well than to say well</span><span style="font-size:13px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">”, 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.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The following link contains the ‘code’, a ‘readme’ file and the corresponding ‘reference paper’. </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Link:   </span><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent"><a href="https://github.com/manikanta-kondeti/codes/tree/master/K-Means">K-means code</a></span></p><br><ol style="margin-top:0pt;margin-bottom:0pt" start="2"><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Implementing </span><span style="font-weight:bold;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">shared memory</span><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent"> object which has the precomputed data: </span></p></li></ol><p dir="ltr" style="line-height:1.44;margin-top:0pt;margin-bottom:5pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">                       </span><span style="font-size:15px;font-family:Arial;color:rgb(51,51,51);vertical-align:baseline;white-space:pre-wrap">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 </span><span style="font-size:15px;font-family:Arial;color:rgb(51,51,51);font-style:italic;vertical-align:baseline;white-space:pre-wrap">shared memory</span><span style="font-size:15px;font-family:Arial;color:rgb(51,51,51);vertical-align:baseline;white-space:pre-wrap">. 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. </span><span style="font-size:15px;font-family:Arial;color:rgb(38,38,38);vertical-align:baseline;white-space:pre-wrap">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.</span></p><p dir="ltr" style="line-height:1.44;margin-top:0pt;margin-bottom:5pt"><span style="font-size:15px;font-family:Arial;color:rgb(38,38,38);vertical-align:baseline;white-space:pre-wrap">P.S : I haven’t used semaphore in the demo as it takes a huge amount of time. </span></p><p dir="ltr" style="line-height:1.44;margin-top:0pt;margin-bottom:5pt"><span style="font-size:15px;font-family:Arial;color:rgb(38,38,38);vertical-align:baseline;white-space:pre-wrap">Link : </span><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap"><a href="https://github.com/manikanta-kondeti/KernelPogramming/tree/master/SharedMemory">SharedMemory example code </a></span></p><br><p dir="ltr" style="line-height:1.44;margin-top:0pt;margin-bottom:5pt"><span style="font-size:15px;font-family:Arial;color:rgb(38,38,38);vertical-align:baseline;white-space:pre-wrap">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. </span></p><br><p dir="ltr" style="line-height:1.44;margin-top:0pt;margin-bottom:5pt"><span style="font-size:15px;font-family:Arial;color:rgb(38,38,38);vertical-align:baseline;white-space:pre-wrap">This is my view on this project and I would be very glad to receive any kind of suggestions or modifications. </span></p><div><span><br></span></div>Thank you,</span><div>Manikanta </div><div>MS by Research,</div><div>LSI, IIIT-H, </div><div>India. </div><div><span><br><p dir="ltr" style="line-height:1.44;margin-top:0pt;margin-bottom:5pt"><span style="font-size:15px;font-family:Arial;color:rgb(38,38,38);vertical-align:baseline;white-space:pre-wrap">  </span></p><div><span style="font-size:15px;font-family:Arial;color:rgb(38,38,38);vertical-align:baseline;white-space:pre-wrap"><br></span></div></span></div></div>