[pgrouting-dev] Gsoc 2013 Preliminary project proposal

[Mukul priya]

Hi ,


             I am a  B.tech fourth year student at IIIT-Hyderabad pursuing
a degree in computer science and engineering and i will be soon pursuing a
Masters Degree in the field of Spatial Informatics and the research topic
that i have been working on is *"In route nearest neighbour querries".*

             Last year i worked on a project that was funded by Honeywell
technology solutions and it gave me a lot of insight about open source
programming and industrial work culture.

I was introduced to pgrouting by *Prof. Venkatesh Raghavan* who visited our
college last summer. i have also used pgrouting for implementing one of my
Honors project.

i have gone through the updated ideas page and i am listing out a topic
that i feel i can contribute to.

*Idea *
Network Partitioning

A very simple method using which it can be done is :


   - *Existence of a natural Hierarchy*

         Generally road networks are organized such that there is some
natural hierarchy for example if we look at the road network of USA we
observe that there are national highways which connect multiple large
regions , inter state roads connect places within these regions , multi
lane roads connect city areas and then there are small roads to connect
individual houses.

           so what we can do is first rank these classes that constitute
the road network and then use the highest level roads to divide the road
network into large regions enclosed by these roads. each of the divided
regions can further be divided again using next lower level road.

           so suppose we have a road network which n classes of different
roads then we can create a tree of depth n-1 where the root of the tree
will represent the entire road network and children of the the root node
will represent the area formed by partitioning the root using the level 1 (
highest ) edges and so on . the nodes will basically represent a smaller
part of the road network.

            The idea seems to be very naive right now but if anyone can
give some feedback whether it is achievable or not or may be suggest some
modifications.

             In route nearest neighbour querries( IRNN) which handle
querries like computation of shortest path , provided that the user wants
to visit facilities F1 , F2 ,.....FN while he/she drives or walks from
source to destination. Network partitioning can optimize these
computations  too as the search space reduces significantly once we have
the partitions. Handling such querries have not been implemented yet. It
will be very helpful if we can have some discussion about whether
implementing it is feasible or not.

             It would be great if someone could give a general idea how  to
go about learning more about the areas mentioned  with respect to the
organization's projects.Specially suggest those ideas which the developers
think are achievable for now . I will also be grateful if somebody can
guide me regarding the development framework of pgrouting so that i get
familiar with the whole framework in the coming days.




Thank you .
Mukul Priya
Lab for spatial Informatics
IIIT-Hyderabad
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130411/febdfeea/attachment.html>