<div class="gmail_quote">Hi all,<div><br></div><div>I am interested in applying the GSoC project, and I want to work on pgRouting. The description of the idea is pasted at the bottom. I want to get some suggestions from you guys. Any suggestion is welcome. And if some previous GSoC students can share your previous applications, that would be great.</div>

<div><br></div><div>In addition, I am looking for a potential mentor.</div><div><br></div><div>Thanks a lot,</div><div>Jinfu</div><div><br></div><div>
        
        
        


<p style="margin-bottom:0in"><a name="1364d4fa69bbe6b0_OLE_LINK3"></a><a name="1364d4fa69bbe6b0_OLE_LINK4"></a><a name="1364d4fa69bbe6b0__GoBack"></a>
<font color="#000000"><font face="Arial, serif"><font><b>Title</b></font></font></font><font color="#000000"><font face="Arial, serif"><font>:
Highway Hierarchies Routing Support for pgRouting</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font><b>Describe
your idea</b></font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>1.
Introduction</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>One
of the main challenges of routing is the huge size of road networks.
Especially, given source node and sink node in long distance,
shortest path computation will be very time consuming. I would like
to improve current routing algorithm by adding highway hierarchies
routing support. </font></font></font>
</p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>2.
Background</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>Routing
is a very common task in GIS, and pgRouting is a famous routing
library which provides routing functions for many GIS software, such
as PostGIS/PostgreSQL. Due to the huge size of road networks, finding
path requires significant computing time, especially for long
distance source and destination. This results in slow response time
and unfriendly user experience.</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>3.
The idea</font></font></font></p>
<p style="margin-bottom:0in"><a name="1364d4fa69bbe6b0_OLE_LINK2"></a><font color="#000000"><font face="Arial, serif"><font>In
fact, this algorithm is not my idea. My work will base on the paper
[P.  Sanders, D. Schultes]. Basically, this algorithm includes two
steps: construct the highway hierarchies; query on the highway
hierarchies. According to their experiments, this new approach can be
about 2000 times faster than the original Dijkstra’s algorithm. The
tradeoff is spending a few hours for generating highway hierarchies.
I want to implement this algorithm in pgRouting library. </font></font></font>
</p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>4.
Project plan</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>5.10-5.20:
Read the source code and talk with the mentor - understand its
structure and working flow</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>5.21-6:10:
Read the paper and start to do some experiments on it – understand
the algorithm</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>6.11-6.30:
Code and test the first step: construction of highway hierarchies</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>7.1-7.5:
Write middle term report</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>7.6-7.20:
Code and test the second step: the query – compare the output with
the output generated by other algorithms</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>7.21-7.31:
Comprehensively test the algorithm and the library - call functions
from other software</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>8.1-8.10:
Improve documents and write final report.</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>5.
Future ideas / How can your idea be expanded? </font></font></font>
</p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>None<br><br>
</font></font></font></p></div></div>