Warnock Inc. Technology Consultation for the Future

In this presentation, I describe how geolocation using data from cell phone towers works. An example of this is the My Location feature in Google Maps Mobile.

Download
PDF/PowerPoint

Because when using Dijkstra's Algorithm as-is, the processing time is pretty high when calculating routes with our current code, we need to optimize the process. The first optimization we did was to end the processing when the end point is found. I ran some tests on the code and the GetMin() function was taking the longest time. This function loops through all existing nodes to find the shortest distance to the next node. We can optimize this if we keep these nodes in order using a Priority Queue.

Now that we have a table of intersections and a table of links, we are ready to calculate the shortest or fastest route. To do this, we will use a graph. In mathematics, a graph is not just an image w/ lines or a pie chart; a graph is a mathematical representation of nodes (points) and edges (lines). This is equivalent to our intersections and streets, or links. To calculate the fastest or shortest path, we must know how the points connect to each other, and what their weight is.

When we created the road segments, we didn't fill in the distance and time information. Now that we have a distance function and speed data, we can fill in distance a time. These two values are need to calculate the shortest and fastest route between two points. Because the distance calculation can take a while, we will do the update in two steps. Use this SQL query to create this data:

USE tiger
UPDATE links
SET links.distance = round(dbo.LatLonRadiusDistance( FRLAT/1000000.0, FRLONG/1000000.0, TOLAT/1000000.0, TOLONG/1000000.0 ), 4)
FROM links

To calculate the time it takes to drive on a road, the speed a person drives must be taken into consideration. This is the cornerstone of improvements to the routing technique. While the speed data we use currently may not be 100% accurate, it is a good starting place, and a good baseline to test our improvements.