Papers
Hierarchical geospatial indexing: Google S2 Geometry and Uber's H3
Isaac Brodsky (Uber engineering post on H3), S2 Geometry project team (official documentation), H3 project team (official documentation) · Public non-academic sources: Uber engineering blog (H3: Uber's Hexagonal Hierarchical Spatial Index, 06/27/2018) and official documentation at s2geometry.io and h3geo.org (version 4.x), 2018
The problem: grouping events by location into cells of a global grid
Uber's engineering post on H3 starts from a practical need: millions of events happen in the marketplace every day, each at a specific point, and information has to be extracted by analyzing an entire city. Analyzing at the finest granularity, the exact location of each event, is hard and expensive; analyzing areas, such as neighborhoods, is far more practical. The solution is a grid system that groups events into cells, for example to measure supply and demand per hexagon and compute dynamic pricing. According to the post, alternatives such as postal code areas have shapes and sizes that are of little use for analysis and change for reasons unrelated to how they are used, while zones drawn by operations teams require frequent updates and define borders arbitrarily. A grid has comparable shapes and sizes across cities and does not change arbitrarily. The post also describes a simple approach, a map projection (such as Mercator) with a square grid laid on top, and points out two flaws: Mercator distorts size heavily, so cells end up with very different areas, and squares have two kinds of neighbor, those that share an edge and those that share only a vertex, which forces the analysis to use more than one set of coefficients. The S2 documentation contrasts traditional geographic information systems, which represent data in flat projections, with the S2 approach: representing everything on a sphere, which allows a worldwide database with no seams or singularities, using a single coordinate system.
S2: cube projected onto the sphere and identifiers along a Hilbert curve
According to the S2 documentation, the library decomposes the unit sphere into a hierarchy of cells. The top level comes from projecting the six faces of a cube onto the sphere, and each cell is recursively subdivided into four children. Each cell is a quadrilateral bounded by four geodesics. The level is the number of subdivisions from the face and ranges from 0 to 30; the smallest ones, at level 30, are called leaf cells, there are 6 times 4 to the power of 30 of them, and each is about 1 cm on a side on the Earth's surface. Points are usually represented by leaf cells, and regions by collections of cells of varying levels. Each cell has a 64-bit identifier, the S2CellId, numbered along a curve that links six Hilbert curves into a single continuous loop over the sphere. Because of this, if two identifiers are close, the cells are also close, which improves locality of reference in indexing. The structure of the identifier of a level-k cell is: 3 face bits, k pairs of bits that choose the child, a 1 bit, and zeros up to 64 bits. Thus, the level can be deduced from the position of the lowest-order 1 bit. To make cell sizes more uniform on the sphere, the library applies a nonlinear transformation between the (s, t) and (u, v) coordinates before projecting onto the globe.
H3: icosahedron, hexagons, twelve pentagons, and aperture 7
The documentation describes H3 as a discrete global grid system, with hexagonal tiling at multiple precisions and hierarchical indexes. The grid is built on the flat faces of an icosahedron circumscribed around the sphere, and the cells are then projected onto the surface by an inverse gnomonic projection. Uber's post justifies the hexagon this way: a hexagon has a single distance between its center and those of its neighbors, versus two for squares and three for triangles, which simplifies analysis and gradient smoothing. Because the icosahedron cannot be tiled with hexagons alone, each resolution contains exactly 12 pentagons, one at each vertex of the icosahedron. The icosahedron is oriented using the Fuller orientation, which, according to the documentation, places the 12 vertices in the ocean; the post says this helps keep pentagons from showing up in Uber's work. Resolution 0 has 122 base cells, 110 hexagons and 12 pentagons. Each subsequent resolution uses aperture 7: each hexagon has one seventh of the area of the previous resolution's hexagon (measured on the icosahedron, before projection onto the sphere). There are 15 finer resolutions beyond 0, and resolution 15 has cells with an area under 1 m². The index is a 64-bit integer whose mode field is 1 for cells, and converting latitude and longitude to an index takes a resolution between 0 and 15.
Trade-offs: exact or approximate contention, neighborhood and region compaction
The H3 documentation compares the two systems. Both use 64-bit integers as cell indexes. S2 uses aperture 4: a square subdivides exactly into four child squares, so an indexed point truncated to the parent cell always stays inside it. In H3 this operation is approximate, because hexagons do not subdivide exactly into seven hexagons; logical containment in the index is exact, but geometric containment is approximate, and the cell boundaries at a given resolution are not affected. When exact borders are needed, the documentation suggests treating the hierarchy as logical and using the grid as an optimization before a precise point-in-polygon test. On the other hand, squares have two classes of neighbors, while hexagons have only one, the one that shares an edge, which simplifies convolutions and smoothing. In both libraries, a region becomes a set of cells at different levels. In H3, the compactCells function does this; in the example from Uber's post, California, which at resolution 6 uses 10,633 cells, ends up with 901 cells of resolutions up to 6, and uncompactCells recovers the original set. In S2, the covering examples show the trade-off: with few cells the covering of a circle wastes area, and allowing more cells approximates the region better, and the cell hierarchy documentation shows Hawaii approximated by 22 cells.
See the ideas at work
Practice the designs that use this paper in the System Design school.