Chapter 16. Temporal Cell Index Types

A discrete global grid system (DGGS) partitions the Earth into a hierarchy of cells, each identified by a 64-bit integer, so that a position becomes a cell identifier and a containment test becomes an integer comparison. MobilityDB supports three of them, and a temporal cell index type records the movement of an object as the sequence of cells it occupies over time.

Figure 16.1, “An AIS vessel track leaving Frederikshavn on the three grids, with the cells the track passes through shaded and a marine protected area in green. The upper row states the whole track at the resolutions whose cells are closest in area and outlines in black the excerpt the lower row states, one resolution finer in each grid. Vessel track and protected areas from the Danish AIS data; basemap © OpenStreetMap contributors.” shows one AIS vessel track leaving Frederikshavn on the three grids, at the resolution of each whose cells are closest in area — 0.57 km² for H3, 0.43 km² for QUADBIN and 0.32 km² for S2 at this latitude — with the cells the track passes through shaded and a marine protected area in green. A temporal cell index records that shaded sequence, so the track is one and the same and each grid states it as a different sequence of identifiers. Asking whether the vessel entered the protected area then becomes an integer test between two sets of identifiers rather than a test between two geometries. The lower row states the excerpt outlined in black above, one resolution finer in each grid, where every cell is roughly an eighth of the area above it and the sequence follows the track closely enough to stand for it.

Figure 16.1. An AIS vessel track leaving Frederikshavn on the three grids, with the cells the track passes through shaded and a marine protected area in green. The upper row states the whole track at the resolutions whose cells are closest in area and outlines in black the excerpt the lower row states, one resolution finer in each grid. Vessel track and protected areas from the Danish AIS data; basemap © OpenStreetMap contributors.

The three differ in the shape of a cell and in how the hierarchy branches. Uber's H3 tessellates the sphere into 122 base cells at resolution 0 and subdivides each into 7 children at every finer resolution, up to 15, so a cell is a hexagon on an icosahedron and its identifier encodes the base cell, the resolution and the hierarchical position. CARTO's QUADBIN is built on the slippy-map (Web-Mercator) tile scheme: a single world cell at resolution 0 subdivides into four equal children at every finer resolution, up to 26, and the identifier encodes a header tag, the resolution and the tile coordinates. Google's S2 projects the six faces of a circumscribed cube onto the sphere and subdivides each face into four children, up to level 30, so a cell is a spherical quadrilateral and the identifier encodes the face, the position along a Hilbert curve and the level.

Each shape buys something. A hexagon has six neighbours all at the same distance from its centre, so an H3 step is the same move in every direction, which is what a flow or a density surface wants. A QUADBIN square is a slippy-map tile, so a cell IS the tile a map server already serves and the identifier converts to the (x,y,z) triple and the quadkey string of that ecosystem. An S2 cell is a quadtree cell of a cube face projected onto the sphere, so the descendants of a cell occupy one contiguous interval of the Hilbert curve and an ancestor test is a pair of integer comparisons. The grids are documented by their authors at h3geo.org, CARTO and s2geometry.io, and the family they belong to at Discrete global grid.

They answer the same questions, so this chapter states each operation once and names the grid only where the answer depends on it. S2 calls a resolution a level; the two words denote the same quantity.

A cell index type shares its on-disk representation with tbigint: both store a temporal 64-bit integer. The distinct SQL type exists so that the type-checker rejects a cell-specific function applied to an arbitrary tbigint trajectory, and the reverse. Casts to and from tbigint are binary-coercion only, zero-cost at run time, and explicit, so a query states ::.

As with other temporal types, a cell index type has four subtypes: Instant, discrete sequence, continuous sequence with step interpolation, and SequenceSet. Cell identifiers are discrete, so linear interpolation between two of them has no meaning and step interpolation is always used.