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. A query like "find drivers within 2 km" becomes a handful of cell lookups over a 10-million-row table. Hexagonal cells put all six neighbors at the same distance from the cell center.
Intuition. Stamp every driver with a grid-cell code based on where they are parked. Same code means same neighbourhood. "Within 2 km" becomes the driver's cell plus the ring around it.
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. Cell shape determines the neighbor ring. A square has eight neighbors at two distances: four edge-neighbors one cell away, four corner-neighbors farther by a factor of root two. A hexagon has six neighbors, each at the same distance from the center, which yields a symmetric ring for a radius query.
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. H3 codes for three Stanford campus buildings and SF Mission. At resolution 8 the three campus buildings map to 8828347417fffff and SF Mission, 29 miles away, maps to a different cell. At resolution 12 the three campus buildings split into three cells, differing in the trailing digits (orange), and SF Mission remains in a different cell.
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. Hashing maps each (lat, lng) to the H3 cell that contains it. Ten million orders start as coordinates. The system computes the cell ID per order and stores orders by that ID. Nearby orders share a cell ID. Distant orders map to different IDs.
Figure 4. A radius query hashes the driver location to one cell, then reads the six adjacent cells that the radius can cross. The query performs up to seven cell lookups. Those seven cell IDs can map to seven different pages, which yields up to seven reads. The read count stays constant as the table grows from ten thousand orders to ten million.
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.