Warnock Inc. Technology Consultation for the Future

Dunbar is a location-based chat tool for mobile devices and phones, as well as other devices. The chat program will let users chat with friends while being notified of their location. The devices obtain your location automatically or let the user manually set their location. Maps of buddies as well as information on their location and distance are available. When a buddy is close to the user, the user is notified. Dunbar is integrated into other applications like Facebook, and provides your status and location to your friends in your Facebook profile.

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