How does maps.google.com select and render search result markers so efficiently?

Question

I've been looking into a number of ways to display a large number of markers on a map recently, and thought that Google must have a very efficient solution to this problem (beyond having massive servers!). If you type, say, 'accommodation' into the map search bar, the map shows about 100 or so points (regardless of zoom level), and more points appear when you zoom in on a certain region. However, there must be millions of points that fall under the 'accommodation' search label, so considerable selection of markers is occurring.

I'm guessing they must use a getBounds approach to filter the markers when the user zooms in/moves about, then perhaps a random selection from those markers. However, that sounds potentially inefficient as the entire database has to be trawled to pick only those points that fall inside the map bounds. Is it simply having enormous computing power that makes Google Maps so fast (most of the time...)? Or is there a more efficient way to do this type of database querying other than the approach detailed above?

I'm building a Rails/Google Maps app that I would like to be able to scale to more than a million points - I definitely don't want to display all the points at once, but I would like to develop a fast search algorithm that isn't hugely taxing on the server to allow a (relatively small) selection of points to be rendered on the map at any one time, in a similar manner to how Google do it. Any suggestions would be most appreciated!

Answer 1

The question can be separated into 2 parts:
1. How to select the points to be displayed.
2. How to display the selected points fast.

Selection can be done with a number of different policies, for example in the case of hotels, which have user ratings, you could select those with the highest rating first. Or perhaps Google get paid for prioritizing some above others. But most likely this is not done in real time!! (just guessing on this one)

Fast display is achieved by means of premade custom tiles. The little red dots are not javascript marker objects, but custom tiles, like this:

http://mt3.google.com/mapslt?lyrs=lmq:1000:hotel|cc:US|h:18b|s:115968771510351694523,m%40130&x=2&y=5&z=4&w=256&h=256&hl=en&style=18,28

Those tiles are created periodically, (say once a day or once a week), and saved, so they are server-cached and ready to use. The mouseover and click functionalities can be achieved by an ajax call that searches only a small table containing only records that correspond to the dots that have been selected and plotted on the tiles. These small tables would be updated every time that a new tileset is created.

Answer 2

You need a spatial index on your data. SQL Server 2008 has this functionality built in. If your database doesn't, then you need to generate a "tile number" from your coordinates and index on that. Your tile number should be unique for every point within a 1km square, for example. You search by tile number for the tiles currently displayed by the view, and you should have an efficient search.

Answer 3

Sonia, that same search tomorrow, next week or next month yields different points though. What google does with 1million results is randomly pull say 1000 out of that large number. So you could do a "random sampling" of points in your query.