Team Members: Dane Brandon, Hardeep Uppal, Tatiana Gershanovich
Google Mentor: Barry Brumitt
Abstract: Calculating driving directions in real-time on large maps is difficult to implement due to the large size of the data set representing the graph and potentially long run time needed for a typical implementation of Dijkstra's algorithm when the start and end points are far apart. In this project we have implemented a modified version of Dijkstra's algorithm in MapReduce to pre-compute the shortest paths to highways from all reachable points in the map. By parallelizing search at runtime into independent segments on subsections of the map, which are then combined into a final path, we can find the distance optimal path between any two points on a map in seconds.
Revised Proposal: At the onset of this project, we had proposed many possible directions for the project hoping, to tackle as many as possible. Due to the difficulty and complexity of computing directions on large scale maps (graphs), our mentor and T.A. alike agreed that returning any directions at all, even sub-optimal, would be a worthwhile goal. We had originally planned on creating subgraphs of the complete dataset based on zoom level, where street types (interstate, highway, city, road, etc…) would only be included as the streets were rendered on the tiles. Directions would be computed top-down, meaning start at the highest zoom-level and compute directions on the interstates only. As the user zooms in, compute more precise directions on the subgraph which corresponds to the tiles being displayed. Provided enough time, we had hoped to create a webpage which would use our tiles rendered from the previous project and add text directions as well as lines overlaid onto the page illustrating the computed path as is typical in most online mapping software.
Current goals: We have chosen to focus on the optimality of directions, distribution of data and computation at runtime in a scalable manner, and speed of the real-time computation of directions. As this is not a web services/design class, and time is limited, we have chosen to sacrifice the graphical interface for text-only directions which are far superior to our original goal. We feel our focus is much more inline with the goals of this class, namely scalable solutions to large problems in a distributed environment. We will likely add a graphical interface at a later time.
**Click on 'Files' button at the bottom right of the page to download the source code, slides and report file. **
