(9) What algorithms is Google using in the geocoding and searching? - Quora

(9) What algorithms is Google using in the geocoding and searching? - Quora

It's the S2 Geometry Library.

The geocode it uses in a nutshell:

• start with a cube map
• create a quadtree with 30 levels on each face
• label both leaves and internal nodes with 64 bits
• use 3 bits for the face index
• use n*2 bits to identify a node at depth n
• add a single 1 bit
• pad with 0 bits as necessary

This code has several nice properties, e.g. the depth of a node can be computed from the index of the least set bit in its code. It's also pretty amazing that when S2 is used to geocode the surface of Earth, the leaf nodes are smaller than 1 cm^2.

Make sure to check the code out though, it has many clever details, such as using the Hilbert curve ordering for labels so that neighboring nodes get close codes.

Areas are represented as sets of nodes, so most operations on areas are simple set operations implemented in a way that eliminates redundancy (ensures that parent nodes absorb their children).

See Geometry on the Sphere: Google's S2 Library for an in-depth explanation.

Read full article from (9) What algorithms is Google using in the geocoding and searching? - Quora