[pgrouting-dev] Gsoc 2013
Mukul priya
mukul2047 at gmail.com
Thu Apr 25 08:06:23 PDT 2013
How much of the network do you have to explore using each algorithm?
This will be reduced significantly while using Astar as we will have a fair
bit of idea about the direction towards which we should proceed.
How does this impact the number of grids you have to load?
Once we have an idea about the direction towards which we should proceed ,
only those grids will be loaded. This will result in loading of less number
of grids.
How does this impact your proposal?
The basic motivation behind the proposal is to make shortest path
computation faster. Number of database querry will be reduced as we will be
fetching lesser number of grids. This will have a positive effect on
computation time.
On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> On 4/25/2013 12:26 AM, Mukul priya wrote:
>
>> Thanks Steve ,I am familar with astar ,It uses a heuristic to guide
>> itself to the destination, there was huge focus on it in our game theory
>> course.
>>
>> Although do point out the advantages it has in real life road network
>> and its importance to my proposal.
>>
>
> How much of the network do you have to explore using each algorithm?
> How does this impact the number of grids you have to load?
> How does this impact your proposal?
>
> -Steve
>
> On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>>>
>> wrote:
>>
>> Hi Mukul,
>>
>> This is a good write up. It largely mirrors out discussion. One
>> thing that needs to change in this is that dijkstra should be
>> replaced with astar.
>>
>> Are you familiar with how these are different?
>> http://theory.stanford.edu/~__**amitp/GameProgramming/__**
>> AStarComparison.html<http://theory.stanford.edu/~__amitp/GameProgramming/__AStarComparison.html>
>> <http://theory.stanford.edu/%**7Eamitp/GameProgramming/**
>> AStarComparison.html<http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html>
>> >
>>
>>
>> Do you see why? and specifically why it matter for this project?
>>
>> -Steve
>>
>> On 4/24/2013 9:10 PM, Mukul priya wrote:
>>
>> ***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 <mailto:mukul2047 at gmail.com>
>> <mailto:mukul2047 at gmail.com <mailto: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 <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>
>> >
>> <mailto:woodbri at swoodbridge.__**com
>>
>> <mailto:woodbri at swoodbridge.**com <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
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> <mailto:pgrouting-dev at lists.__**osgeo.org <http://osgeo.org>
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >>
>> http://lists.osgeo.org/____**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> **>
>> <http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>__>
>>
>>
>>
>>
>>
>>
>> ______________________________**___________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**
>> osgeo.org <pgrouting-dev at lists.osgeo.org>>
>> http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>> ______________________________**___________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>>
>>
>> ______________________________**_________________
>> 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>
>>
>>
> ______________________________**_________________
> 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/eace31d7/attachment-0001.html>
More information about the pgrouting-dev
mailing list