Case Study 2.1: How Uber and Google Maps use Geo-hashing
Concept. Geo-hashing converts a 2-D (lat, lng) coordinate into a 1-D grid key, turning "find drivers within 2 km" into a handful of cell lookups instead of a 10-million-row table scan. The grid is hexagonal, not square, because a hexagon's six neighbours are all the same distance away.
Intuition. Stamp every driver with a grid-cell code based on where they are parked. Same code means same neighbourhood. "Within 2 km" becomes a few cell lookups, the driver's cell plus the ring around it, instead of distance arithmetic across 10 million rows.
The dumb way, and the obvious fix
Food delivery and mapping live or die on how fast you can group nearby orders and assign them to drivers. Picture a database of 10 million active orders with coordinates like these:
orders = [(37.788022, -122.399797), (37.788122, -122.399797), (37.788022, -122.398897)]
When a driver opens the app and you want orders within 2 km, the naive query runs an ST_Distance(driver_loc, order_loc) calculation across all 10 million rows. That is a full table scan: 10 million IOs, on every request. During a lunch rush it saturates the database.
The fix is to stop measuring distances and start grouping by location. Chop the map into a grid, give each cell a short code, and store orders by their cell. Nearby orders share a code, so "find nearby" becomes "find the same code." The only real question is what shape the grid cells should be, and that choice turns out to matter.
First idea: square cells
Start with the obvious shape, squares. This is the classic geo hash. Cut the world into a grid of squares, then cut each square into a smaller grid, again and again; each cut adds one character to the code. Close locations agree all the way down, so they keep a long shared prefix, and a prefix match finds the neighbourhood. At 5-character precision (37.788022, -122.399797) is 9q8yy, a cell about 5 km across.
Squares group points fine. The trouble shows up on the radius query. A point near a cell edge has close neighbours in the next cell over, so you can never read just the one cell; you read the cell plus its ring of neighbours. And a square's ring is uneven: its four edge-neighbours sit one cell away, but its four corner-neighbours are farther, by a factor of root two. The ring you are forced to read is lopsided, so "within 2 km" comes out sloppy at the corners.
Why hexagons, not squares
Figure 1. The shape of the cell decides the shape of the ring. A square has eight neighbours at two distances: four edge-neighbours one cell away, four corner-neighbours farther by a factor of root two, so the ring a radius query must read is lopsided. A hexagon has six neighbours, every one exactly the same distance from the centre, so the ring is even in all directions. That uniform neighbour distance is the whole reason map systems grid the world into hexagons.
A hexagon fixes the lopsided ring. Each of a hexagon's six neighbours is exactly the same distance from the centre, so the ring you read for a radius query is even in every direction. That one property, uniform neighbour distance, is why Uber and Google grid the world into hexagons rather than squares.
Uber H3: hexagons in practice
Uber's H3 partitions the earth's surface into hexagons at a chosen resolution (see H3 vs S2 comparison). You pick the resolution from the precision you need: at resolution 8 close locations share a cell ID, while at resolution 12 buildings on one campus differ by a few characters.
Click to expand. SF Mission versus three Stanford buildings (NVidia, Packard, Gates): nearby pins keep nearly identical H3 codes at every zoom level; the far one does not.
Here's how h3.latlng_to_cell converts coordinates into hexagonal cell IDs:
import h3
# lat/lngs from SF mission, Stanford NVidia, Packard, Gates Buildings
locations = [(37.788022, -122.399797), (37.428226, -122.174722),
(37.429749, -122.1735490), (37.429761, -122.173290)]
for res in [8, 12]: # H3 resolutions
for l in locations:
cell_id = h3.latlng_to_cell(l[0], l[1], res)
print(f"@res[{res}]: {cell_id}")
Figure 2. The three Stanford campus buildings versus SF Mission, computed with H3. At resolution 8 (zoomed out) the three campus buildings get the identical code 8828347417fffff, one shared cell, while SF Mission, 29 miles away, is a different cell. Zoom in to resolution 12 and the three campus codes split into separate cells, differing in the fine digits at the end (orange); SF stays different. Nearby points share a cell and far ones do not, so a shared code works as a proximity test.
The hash and the lookup
With hexagons chosen, the scheme is two steps: hash each location to its cell, then look up the query's cell plus the ring of neighbour cells the radius touches.
Figure 3. The first step is the hash. Ten million orders start as raw (lat, lng) pairs. Lay H3's hexagons over the map and every order takes the code of the hexagon it lands in. Nearby orders, like three buildings on one campus, share a code; a far order in SF gets a different one. The hash is just which cell a point falls in, and points that share a cell are stored together.
Figure 4. The second step is the lookup, and this is the part to get right: it is fast, but it is not one read. A radius query hashes the driver's location to one cell, then reads the six neighbour cells too, because the radius crosses cell borders. That is up to seven cell lookups, and those seven cell IDs can sit on seven different pages, so up to seven reads. The win is not that it is a single read; it is that seven is constant, the same whether there are ten thousand orders or ten million, instead of scanning all of them.
Takeaway: Geo-hashing turns a 2-D (lat, lng) pair into a 1-D grid key, so "find drivers within 2 km" becomes a handful of cell lookups, the query cell plus its ring of neighbours, instead of distance math over millions of rows. That count stays around seven no matter how many millions of orders there are, and hexagons keep the ring even. It is an exact spatial hash; similarity hashing for high-dimensional data is LSH and vector hashing, next.