data structure to support google/bing maps

Question

I was wondering what the data structure is in an application like google/bing maps. How is it that the results are returned so quickly when searching for directions? what kind of algorithms are being used to determine this information?

thanks

Answer 1

I was wondering what the data structure is in an application like google/bing maps.

To the user: XHTML/CSS/Javascript. Like any website.

On the server: who knows? Any Google devs around here? It certainly isn't PHP or ASP.net...

How is it that the results are returned so quickly when searching for directions?

Because Google spent years, manpower and millions of dollars on building up the architecture to get the fastest server reaction time possible?

What kind of algorithms are being used to determine this information?

A journey planner algorithm.

Answer 2

I'm not sure of the internal data structure, but it may be some kind of 2D coordinate based tree structure that only displays a certain number of levels. The levels would correspond to zoom factors, so you could ignore as insignificant things below, say, 5 levels below the current level, and things above the current level.

Regardless of how it's structured, here's how you can use it:

http://code.google.com/apis/maps/documentation/reference.html

Answer 3

For this sort of application, you would want some sort of database to represent map features and the connections between them, and would then need:

1. spatial indexing of the map feature database, so that it can be efficiently queried by 2D coordinates; and
2. a good way to search the connections to find a least-cost route, for some measure of cost (e.g. distance).

For 1, an example would be the R-tree data structure.

For 2, you need a graph search algorithm, such as A*.

Answer 4

I would think of it as a computational geometry problem. When you click on a particular coordinate in the map and using that information, can get the latitude and longitude of that location. Based on the latitude and longitude and the level of zoom, the place can be identified.

Once you have identified the two places, the only problem for you is to identify the nearest route. Now this problem is finding the shortest path between two points, having polygon blocks between them(which correspond to the places which contains no roads) and the only possible connections are roads. This is a known problem and efficient algorithms exist to solve this.

I am not sure if this is what google is doing, but I hope they do something on these lines.

I am taking computational geometry this semester. Here is the course link: http://www.ams.sunysb.edu/~jsbm/courses/545/ams545.html. Check them if you are interested.

Answer 5

Look up a paper about Highway Dimension from google authors. The idea is to precompute the shortest path between important nodes and then route everything through those. You are not going to use residential streets to go from LA to Chicago save for getting on and off the freeway at both ends.