Grids, Tiles, and Organizing Location Data

What a Decimal Place Is Worth

Most grids start from plain coordinates, so it helps to know how much ground one digit covers. A degree of latitude is about 111 km everywhere on Earth, and each extra decimal place divides that by ten.

Those figures hold for latitude. East to west, the same step shrinks with the cosine of the latitude, because lines of longitude converge toward the poles. A step of 0.01° of longitude is 1.11 km at the equator, about 0.85 km at 40° north, and about 0.56 km at 60° north.

Decimal places describe how finely a position is written down, not how well it was measured. A reading from a phone can be off by several meters, so digits past the fifth decimal place are usually false precision: they look exact and carry no real information.

The Simplest Grid: Rounding Coordinates

The quickest spatial index needs no library at all. Round or truncate every latitude and longitude to a fixed number of decimal places, and all the points that end up with the same pair of numbers belong to the same cell. Round a city's bike-share stations to three decimal places and each one lands in a box about 111 m tall. To find the stations near a rider, look in the rider's box instead of scanning the whole city.

The method takes one line of arithmetic, and anyone can read the result. It has two weaknesses:

• Cells change shape. Each box keeps its height and gets narrower toward the poles, so a cell in Oslo covers much less ground than a cell in Singapore.
• Edges split neighbors. Two coffee shops on opposite sides of a street can fall into different cells if a cell boundary happens to run down the middle of it.

The second is known as the edge problem, and every grid in this guide shares it. The usual answer is to search the cell that holds the point and the cells around it, then measure the real distance to whatever turns up.

Geohash: A Grid Cell as a Short String

A geohash, introduced in 2008 by Gustavo Niemeyer, packs both coordinates into one short piece of text. It is built by halving the world again and again. Is the point in the western or the eastern half? That is one bit. Is it in the southern or the northern half of that? That is the next. The bits alternate between longitude and latitude, and every five of them are written as one character from a 32-symbol alphabet of digits and lowercase letters.

The longer the string, the smaller the cell:

Cells that share a prefix are nested. The cell dr5r7p4 lies inside dr5r7p, which lies inside dr5r7. That makes prefix search possible: any database that can find text starting with dr5r7 can return everything inside that cell.

The edge problem returns in a sharper form. Two points a short walk apart on either side of the prime meridian in Greenwich, London, have geohashes that begin gcp and u10, with not one character in common. A shared prefix means two points are close; a different prefix does not mean they are far apart. Like rounded coordinates, geohash cells also narrow toward the poles.

Map Tiles and Quadkeys

The tiles that draw a web map double as a grid. At zoom level 0, one square tile shows the whole world. Each zoom level splits every tile into four, so zoom level z divides the world into 2^z by 2^z tiles. A tile is addressed by three numbers, z/x/y: the zoom level, the column counted eastward from the 180° meridian, and the row, which in the most common convention is counted down from the top.

A quadkey writes the same address as a single string of the digits 0 to 3. Each digit says which of the four quarters to step into at the next zoom level, so the length of the string is the zoom level, and a tile's quadkey begins with the quadkey of the tile that contains it.

Latitude, longitude     40.6892, -74.0445
Geohash, 7 characters   dr5r7p4
Tile, z/x/y             15/9644/12322
Quadkey, zoom 15        032010110301120

The tile pyramid is drawn on the Web Mercator projection, which flattens the globe into a square and stretches it toward the poles. A tile at 60° north covers ground half as wide and half as tall as a tile at the equator with the same zoom level. The projection also stops at about 85° north and south, so the poles are not on the map at all.

S2: Squares on a Cube

S2, developed at Google, avoids flattening the whole planet onto one sheet. Picture the Earth inside a cube. S2 projects the surface onto the cube's six faces, then divides each face into four cells, each of those into four more, and so on. The result is a quadtree on every face, with levels that run from 0 (a whole face) to 30 (a cell about a centimeter across). Cells at one level are similar in size all over the globe, though not identical.

Every cell has a 64-bit number as its ID. The cells are numbered along a Hilbert curve, a space-filling path that winds through every cell and always moves to an adjacent one. Because the path never jumps, cells that are close on the ground tend to have IDs that are close in value, and all the cells inside a larger cell form one unbroken range of numbers.

H3: Hexagons

H3, developed at Uber, covers the globe with hexagons instead of four-sided cells. A sphere cannot be tiled with hexagons alone, so each resolution also contains exactly 12 pentagons. There are 16 resolutions, numbered 0 to 15, and each finer resolution has cells with roughly one seventh of the area.

The appeal of a hexagon is its neighbors. A square cell has four neighbors that share an edge and four that touch only at a corner, and the corner neighbors are farther away. A hexagon has six neighbors, all sharing an edge and all the same distance away, center to center. That suits questions about movement and density, such as how deliveries spread from one zone to the next.

The trade-off is the hierarchy. Seven small hexagons cannot exactly fill a larger one, so the children only approximately cover their parent.

Tree Indexes: Organizing the Data, Not the Ground

Every scheme so far carves up the Earth in advance, whether or not anything is there. Tree indexes work the other way around: they are built from the data, so their structure follows the points and shapes.

R-Trees

An R-tree, described by Antonin Guttman in 1984, draws a bounding rectangle around each small group of nearby objects, then groups those rectangles under larger ones, up to a single root. A search skips every branch whose rectangle does not overlap the area of interest. R-trees handle objects with size, such as delivery zones or lake outlines, as easily as points, and they are the standard index in spatial databases.

Quadtrees

A quadtree starts with one square around all the data and splits any square holding too many points into four. It grows deep where data is dense, as in a city center, and stays shallow where data is sparse. The tile pyramid is a quadtree that has been split evenly everywhere.

K-d Trees

A k-d tree cuts the set of points in half along one coordinate, then cuts each half along the other, alternating as it goes down. It answers "which point is nearest?" quickly for a fixed set of points, such as a list of weather stations, and is less suited to data that changes constantly.

Comparing the Schemes

Each scheme strikes its own balance of simplicity, evenness, and flexibility.

What Spatial Indexes Are Used For

• Nearby search: The index narrows millions of candidates to the contents of a few cells or branches, and exact distances are calculated only for what is left.
• Grouping and counting: Assigning every point to a cell and counting the points per cell is the basis of a heat map, whether it shows taxi pickups or lightning strikes.
• Splitting data across servers: A very large dataset can be divided by cell, so that a question about one region goes only to the machines that hold it.

Common Pitfalls

• The edge problem: A search that looks in only one cell will miss neighbors just across the boundary.
• The antimeridian and the poles: Longitude wraps at ±180°, so cells on either side of that line are neighbors even though their coordinates and geohashes look nothing alike. Latitude-longitude cells shrink to slivers near the poles, and Web Mercator tiles stop short of them.
• Cells that are not equal in area: Counting points per cell is a fair comparison only if the cells cover the same amount of ground. Rounded coordinates, geohashes, and Mercator tiles all cover less ground at higher latitudes, and even S2 and H3 cells vary somewhat in size.
• Confusing precision with accuracy: A long geohash or a very fine cell names a spot smaller than a coin. If the position came from a phone, the true location could still be several meters away.