[pgrouting-dev] Gsoc 2013
Mukul priya
mukul2047 at gmail.com
Wed Apr 24 18:10:35 PDT 2013
* **Name*:Mukul Priya
*Country:*India
*School and degree*: International Institute Of Information
Technology-Hyderabad ,
B.Tech + Masters in computer Science And
Engineering
*Email*:mukul2047 at gmail.com
*Phone*:+91 9885991061
*OSGeo project(s*):pgRouting
*Title:* A partitioned approach to on demand increment graph assembly for
pgRouting.
* Describe your idea*
*1. Introduction*
pgRouting has been working towards providing routing functionality
on a PostGis/PostgreSql Geo spatial
database. It already has support for shortest path algorithm like astar
,dijkstra , tdsp and trsp .But for a very
large network, routing becomes time consuming. Network partitioning is
one such way which can prove to
be helpful in improving the overall time efficiency of routing querries.
The main idea here is to first partition
the whole network using a Quad tree approach and when the shortest path
is computed these partitions are
loaded on demand. hence , there is an on demand incremental graph
generation.
The project aims at designing and implementing a Shortest Path
algorithm on an on demand incremental
Graph using a network partitioning approach.
*2. Background*
Considering the present status where pgRouting has support for
shortest path algorithm like astar etc.
Looking at their implementation details we can observe that the graph is
configured dynamically for all
of them before computation.My proposal will also be on the same track and
for very large networks
where the distance between source and destination can be very large , the
response time will be
significantly lesser and memory wise too it will be lot more efficient.
Presently they don't use any partitioning
approach so it will prove to be a good addition to their support for
shortest past algorithms.
*3. The idea*
There are two major components of my idea .
-
*Network Partitioning*
For this part we can use a quad tree approach. Say , we start with a
square and a condition like maximum
number of nodes that can reside in a square . if the number of nodes
in the square is greater than the max
condition we further quarter it into four squares and allot the
nodes appropriately to each of them.All these
squares can be called grids and they all will be addressed uniquely
using a grid cell number .Each node
will be assigned a grid cell number based on the grid they are lying
inside.
We will have data structures to address edges as they can
remain contained in either one grid cell
or span across a number of grid cells.the idea is to first flag
such edges and store the grid cell numbers
of the grids that the edge crosses/intersects.
-
*On demand graph generation and Routing.*
The idea here is to first identify the grid cell initially
and then fetch the edges that are associated with
that grid. These are the edges that will get appended to the present
graph and the graph will keep growing
dynamically this way. we will have appropriate database tables
addressing the above issue such that
we are able to fetch the required edges quickly using a database
querry.
The implementation details for the above are :
we will first partition the whole graph using the quad tree approach
and each node/vertex will be assigned
a grid cell number so we can have database table for the assigned
nodes and edges like :
CREATE TABLE vertex{
id Node_id \\ unique for each node.
cell grid_cell_number; \\ the grid in which the node
lies.
geometry;
}
CREATE TABLE edge {
int id ;
Int node_a;
int node_b; \\ the connecting nodes
// we can have other parameters like traversal cost and return cost.
}
using the tables we can then fetch the edges form edge table
using simple database querry once
we are provided with the grid cell number very easily.
In short the summary of the whole idea is :
Step1: Fetch the start node , get the related Grid cell number.
Step 2: Increment the graph by fetching all the items related to that grid.
Step3 : Check for boundary nodes ( this is done while we are partitioning)
or target node .
Step 4: On hitting a boundary node
{
check if the connected grid is loaded and continue if it is
or we extend the graph with the new grid and continue with
the routing;
}
or On hitting the target Node
{
stop;
}
*4. Project plan*
I will have about 12 weeks to implement the project. The tentative
schedule is as follows:
Before 17th June : Get familiar with the development environment of
pgRouting and test some demos.
week 1-2: Discuss and Define the various data structures and data
table that will be required.Prepare the
Overall implementation architecture.
week 3-4- Discuss and Implement network partitioning using quad tree.
week 5-8 -Start coding for on demand graph generation and routing
using Dijkstra. In between Prepare mid-term
report.
week 9 - Integration with pgrouting .
week 10-12- Testing and Bug fixing. Draft Final report and
documentation.
*
5. Future ideas / How can your idea be expanded? *
It can be integrated with other shortest path algorithms like astar
etc. which pgrouitng provides.For time dependent
shortest path computation, it will greatly reduce the updating cost as
we will be updating the cost of only those edges
that are contained in the grid cells that are loaded.
In route nearest neigbour querries can also be implemented using the
partitioning approach.Overall we can
expand this approach to various other algorithms.
*Explain how your SoC task would benefit the OSGeo member project and more
generally the OSGeo Foundation as a whole:*
The proposed idea will significantly improve the performance of
shortest path finding algorithms.This will have a
positive effect on the user base of pgRouting. For various software
paltforms or applications that are using this library ,
the response time will significantly improve.
*
Please provide details of general computing experience:
*
I generally use ubuntu ( 12.04) for all my academic purposes and windows 7
for entertainment only. I am familiar with Fedora also.
C++ is the language that i use most ( programming purposes). For
implementing various course projects i have used C++ ,python ,Java and
matlab.
I have no experience with hardware. The only experience that i had with
networking was during my computer network course.
*
Please provide details of previous GIS experience:*
I am a part of "Lab for Spatial Informatics" which is the only lab in India
devoted to GIS applications and learning. I am familiar with and have used
almost all the open source GIS platforms like Quantum , OpenJump,
ILwis,Grass. We have our own rendering platform that was developed by our
lab.(LSI viewer)
*Please provide details of any previous involvement with GIS programming
and other software programming:*
I am very much familiar with Gdal/OGR as i used it extensively while
implementing an outsourced project of Honeywell
Technology . I have played a lot with ESRI shape files.
*Please tell us why you are interested in GIS and open source software:*
I was very impressed with google earth when it was launched way back in
2004.GIS platforms like quantum and Openjump were introduced to me when i
was in my second year and then i joined Lab for spatial informatics that is
in our college based on my interest in this area.
open source platforms provide an opportunity to learn . The best part is
you can always create or develop something that you are interested in and
there are people who will always be there to help you if you are stuck.
*
Please tell us why you are interested in working for OSGeo and the software
project you have selected:*
It will be huge learning experience since i have been using platforms like
Qgis , Gdal ,PostGis etc which come under Osgeo
I chose pgrouting because the algorithms that they have implemented are
related to my masters topic and it will be great if i get an insight about
how these were implemented on a much larger scale.
*Please tell us why you are interested in your specific coding project:*
Implementing routing algorithms for real world networks is actually very
challenging.its a challenge to come up with good approaches so that the
computation cost and response time is both reduced.
*Would your application contribute to your ongoing studies/degree? If so,
how?*
I am pursuing my Masters and my topic is closely related to my proposal .
If the results are impressive , i might get a publication in this area.
*Please explain how you intend to continue being an active member of your
project and/or OSGeo AFTER the summer is over:*
I was always interested in open source programming but never knew where to
start . GSOC provides an opportunity for beginners like me to take a dive
in the area open source programming. i have other ideas like implementing
IRNN ( In route nearest neighbour querries) which can be implemented within
pgRouting.I have other intentions like working for bigger projects like
Quantum Gis or Grass.I will be contributing to the community forum and will
always try to improve things.
*Do you understand this is a serious commitment, equivalent to a full-time
paid summer internship or summer job?*
Yes, I understand that this is a serious commitment and will try to give my
best and work in a professional manner.
*Do you have any known time conflicts during the official coding period?
(June 17 to Sept. 27)*
No .
On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:
> On 4/24/2013 2:34 PM, Mukul priya wrote:
>
>> Hi Steve and Daniel ,
>>
>> I have posted my proposal on Melange Gsoc system. Do have a look at it.
>> Waiting for feedback and suggestions.
>>
>
> Can you post a link to your proposal? or the text of it here also. I can
> never find anything in Melange or I may not have visibility to it yet as I
> just applied as a mentor.
>
> Thanks,
> -Steve
> ______________________________**_________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130425/c43f4d1a/attachment-0001.html>
More information about the pgrouting-dev
mailing list