WingNews logo WingNews GitHub [2]
top | item 21754060

Ask HN: How was Google maps made?

16 points| whatitdobooboo | 6 years ago | reply

I know this is broad - but I cant find much information on how Google Maps or any GIS is made. Does anyone have any links/direction that explains this better?

Edit/Clarification: I am asking from a technology/programming standpoint

8 comments

order
[+] mtmail|6 years ago|reply
Go to an OpenStreetMap like https://www.openstreetmap.org/#map=17/36.16567/-115.15036 and click the 'layer' icon on the right-hand side. This lead to https://www.openstreetmap.org/#map=17/36.16567/-115.15036&la...

You will see all kind of objects (points, ways, polygons). Click on each will reveal a list of key-value pairs, e.g. the name of a street or if it's one-way. What key and value are use depends on the provider. I think Google Maps started with NavTec licensed database.

The data is put into a database (OpenStreetMap: postgresql). Renderer servers do SQL queries for a location and create PNG images (https://mapnik.org/). Similar (more complex) with vector output which is usually rendered in the client, e.g. in the browser (https://github.com/mapbox/mapbox-gl-js)

Later Google decided to skip NavTec and created their own database. They already had the StreeView cars which took photos of the whole USA. In a clean-room environment (no outside internet access) hundreds of employees traced the GPS tracks and photos from StreetView. Months-long and at huge cost. Even if it cost them a billion USD, it was cheaper long-term than paying the licence fees. Then repeat for more countries.

The book "Never Lost Again" (https://www.amazon.com/dp/B07CHPY6B9/) covers the early days from a project, not engineering, point of view.

If you want to play with the technology https://switch2osm.org/ has good guides.

[+] satvikpendem|6 years ago|reply
For one of our classes, we implemented a Google Maps clone, complete with turn by turn navigation as well (although no AI voice, just text). You can do the same if you wish [0]. Note that this project took us a semester, it might take you the same amount of time.

The main insight is that 2D data can be represented by quad-trees, like binary trees but with 4 branches rather than two. This enables you to break up a square are into 4 parts, one for each branch, and further subdivide them. In each branch, you can store some information, such as a location or city. If there are two in a leaf, you break them down until there is only one piece of information in each leaf. This is just one type of quad-tree, there are others. Some subdivide each square evenly, some don't.

Curiously, you can do the same sort of thing with oct-trees, with 8 leaves. In general it seems that for whatever number of dimensions N, you need a 2^N ary tree to represent its internal data. A binary tree works for a 1D line, everything to the left of the line and right of the line (this is how binary search works); quad-trees for northeast, northwest, southeast, southwest; oct-trees for those four, plus front and back; and so on.

[0] http://www.cs.umd.edu/users/meesh/420/ProjectBook/

[+] rgovostes|6 years ago|reply
I recall that in Google’s early days they held a competition where they published a corpus of thousands of crawled webpages and invited developers to do something novel with the data.

The winner used pattern matching to identify addresses, then geocoded them using the US Census Bureau’s TIGER database. Thus it was possible to associate fairly accurate locations to a page, which enabled local searches and a number of other products.

Someone please correct me or fill in details I’ve forgotten.