Why Uber Uses Hexagons to Find Your Driver: H3 Geospatial Indexing Explained

When you open Uber and see five nearby drivers materialize on your map within milliseconds, you're watching one of the harder problems in distributed systems get solved in real time. The "find things near me" query seems simple until you're running it millions of times per second across a database of millions of moving points on a sphere.

Uber's solution? Hexagons. Lots of them. Specifically, the H3 geospatial indexing system — an open-source library that divides the entire Earth into a hierarchical grid of hexagonal cells, each with a unique 64-bit identifier.

The Problem: Why Proximity Search Breaks at Scale

The naive approach to finding nearby drivers is a distance calculation: measure the distance from your location to every driver, sort by distance, return the closest five. This works fine for 100 drivers. It becomes a performance nightmare at 100,000.

Traditional spatial databases use R-trees or quad-trees to partition space into rectangular regions. These structures improve query performance but have critical weaknesses:

  • Rectangles have edge discontinuities. A point 1 meter across a grid boundary might land in a completely different partition, requiring multi-cell queries that kill performance.
  • Lat/lon bounding boxes distort near the poles. A "square" degree of longitude at the equator covers vastly more area than at 60° latitude, leading to uneven data distribution.
  • No natural hierarchy. Moving between zoom levels requires recalculating indexes, making multi-resolution queries expensive.

Uber needed something better: a spatial index that could handle billions of points, support efficient range queries, work globally without distortion, and scale gracefully from street-level precision to city-wide searches.

Enter H3: The Hexagonal Grid System

Developed by Uber's engineering team and open-sourced in 2018, H3 (Hexagonal Hierarchical Spatial Index) divides the Earth into 122 base hexagons, then recursively subdivides each hexagon into seven children. This creates 16 resolution levels from ~1,000 km (resolution 0) down to ~0.5 meters (resolution 15).

Every location on Earth maps to a unique hexagon at each resolution. A point in San Francisco might be:

  • 8428309ffffffff at resolution 4 (~100 km hexagons)
  • 8828308281fffff at resolution 8 (~500 m hexagons)
  • 8f28308280c8461 at resolution 15 (~0.5 m hexagons)

These IDs are the secret sauce. Because H3 uses a hierarchical encoding, you can:

  1. Convert any lat/lon to a hex ID in constant time — no database lookup required
  2. Find neighbors with bitwise operations — each hexagon has exactly 6 neighbors (except the 12 pentagons at the icosahedron vertices)
  3. Zoom in/out by truncating the ID — parent-child relationships are encoded in the bits
  4. Index by hex ID instead of coordinates — turning a 2D spatial query into a simple equality check

Why Hexagons Beat Squares

The choice of hexagons over squares isn't aesthetic — it's mathematical:

Uniform neighbor distance. Every hexagon touches its six neighbors at the same distance from the center. With squares, you have four edge neighbors (distance = 1) and four corner neighbors (distance = √2). This 41% distance variance breaks proximity algorithms.

Better sampling coverage. When you need to cover an area with points, hexagonal grids require ~13% fewer points than square grids for the same coverage uniformity (this is why bees use hexagons).

No preferred direction. Square grids have horizontal/vertical bias. Hexagons have rotational symmetry, which matters when you're modeling real-world phenomena that don't align to compass directions.

Efficient k-ring queries. Finding all hexagons within k steps is trivial with H3's kRing() function — critical for "find drivers within 2 km" queries. With quad-trees, this requires complex boundary calculations.

How Uber Uses H3 in Production

Here's the simplified flow when you request a ride:

  1. Your phone sends lat/lon (37.7749, -122.4194)
  2. App converts to H3 index at resolution 8: 8828308281fffff
  3. Query expands to k-ring (e.g., k=2 gives this hex plus all hexagons within 2 steps = ~1.5 km radius)
  4. Database lookup WHERE h3_index IN ('8828308281fffff', '88283082817ffff', ...)
  5. Drivers in those hexagons returned — typically 5-50 candidates
  6. Client-side haversine sort to rank by exact distance

Because drivers continuously update their H3 index as they move, Uber's dispatch system can query by indexed hex IDs instead of running expensive geospatial calculations on every query. At Uber's scale (75+ million riders, 5+ million drivers globally), this architectural choice saves millions in infrastructure costs.

Grab (Southeast Asia's super-app) uses the same approach. Their engineering blog notes that switching to H3 reduced their proximity query latency by 60% while supporting 3x more concurrent requests per node.

When Should You Use H3?

H3 excels when you need:

  • High-throughput proximity queries (delivery services, ride-hailing, IoT sensor networks)
  • Geospatial aggregation (heatmaps, density analysis, spatial joins)
  • Multi-resolution analysis (zooming between city-wide and street-level views)
  • Global coverage without projection distortion

It's overkill if:

  • You have <10k points and infrequent queries (PostGIS is fine)
  • You need sub-meter precision routing (use road network graphs)
  • Your data is highly localized (a single-city R-tree might be simpler)

Getting Started

H3 has official bindings for Python (h3-py), JavaScript (h3-js), Java (h3-java), and Go (h3-go). PostgreSQL users can install the h3-pg extension for native SQL support:

CREATE EXTENSION h3;

SELECT h3_lat_lng_to_cell(POINT(37.7749, -122.4194), 8);
-- Returns: 8828308281fffff

SELECT h3_grid_disk(h3_index, 2) FROM drivers;
-- Returns all hexagons within 2 steps

The Takeaway

The next time you see "drivers near you" load instantly, remember: you're not watching a brute-force distance calculation. You're watching billions of moving points get indexed into hexagons, queried by bitmask operations, and returned from a spatial index that covers the entire planet.

H3 is what happens when you combine solid geometry, clever encoding, and real-world scale requirements. It's open source, battle-tested at Uber scale, and available for your next mapping project.

Just maybe don't mention the 12 pentagons. They're... mathematically necessary edge cases we don't talk about.

Resources: