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