Uber H3: Hexagonal Hierarchical Geospatial Indexing

The Problem with Maps

Imagine you’re building Uber’s surge pricing system. You need to answer questions like:

• Which areas have high rider demand right now?
• How many available drivers are in a 2km radius?
• Should we increase prices in downtown Manhattan?

The naive approach? Use raw latitude/longitude coordinates and calculate distances between every rider-driver pair. For 100,000 active users in a city, that’s potentially 10 billion distance calculations per second.

There has to be a better way.

What is H3?

H3 (Hexagonal Hierarchical Geospatial Indexing System) is Uber’s open-source solution to efficiently partition the entire Earth into hexagonal cells. It transforms messy geographic coordinates into clean, structured indexes that make geospatial queries blazingly fast.

Think of H3 as a database index for the physical world. Just like how a B+ Tree index speeds up database queries, H3 speeds up location-based queries by organizing coordinates into a hierarchical grid.

Key Terminology and Concepts

Before diving deeper, let’s establish the fundamental concepts you’ll encounter throughout this series:

1. H3 Index: A unique 64-bit integer that identifies a hexagonal cell at a specific resolution. Example: 8928308280fffff

2. Resolution: H3 supports 16 resolution levels (0-15). Resolution 0 divides Earth into ~122 large hexagons. Resolution 15 creates hexagons ~0.9m² in area.

3. Cell: A hexagonal region on Earth’s surface identified by an H3 index.

4. Parent/Child Cells: Each hexagon at resolution N is subdivided into 7 hexagons at resolution N+1 (1 center + 6 surrounding).

5. Neighbors: Adjacent hexagons that share an edge. Each hexagon has exactly 6 neighbors (except at pentagon locations).

6. k-Ring: All cells within k steps from a given cell. k-Ring of 1 returns the cell plus its 6 neighbors (7 total).

7. Icosahedron: A 20-sided polyhedron used as the base shape to project Earth’s sphere into a flat grid.

Why Hexagons?

You might ask: why not squares or triangles? Hexagons have unique mathematical properties that make them superior for geospatial indexing.

Uniform Distance

Hexagons: Every neighbor shares an edge with the center hexagon. The distance from the center to every neighbor’s center is identical.

1
    ___       ___       ___
2
   /   \     /   \     /   \
3
  / N1  \___/  N2 \___/  N3 \
4
  \     /   \     /   \     /
5
   \___/  C  \___/ N4  \___/
6
   /   \     /   \     /
7
  / N5  \___/  N6 \___/
8
  \     /   \     /
9
   \___/     \___/
10

11
Distance from C to every neighbor = d

Squares: Diagonal neighbors are √2 times farther than edge neighbors (1.414x difference).

1
┌─────┬─────┬─────┐
2
│ N1  │ N2  │ N3  │  Distance C→N2 = d
3
├─────┼─────┼─────┤  Distance C→N1 = d√2 (1.41x farther!)
4
│ N4  │  C  │ N5  │
5
├─────┼─────┼─────┤
6
│ N6  │ N7  │ N8  │
7
└─────┴─────┴─────┘

This distance uniformity matters because:

• Gradient smoothing: Heat maps and density visualizations have consistent transitions
• Accurate proximity: 1-hop neighbors truly represent “nearby” without distance distortion
• Simpler algorithms: No special cases for diagonal vs. edge neighbors

Better Coverage

Hexagons have the highest area-to-perimeter ratio of any shape that tiles a plane (except circles, which don’t tile).

This means:

• Less “edge effect” when analyzing regions
• Better representation of circular service areas (2km radius around a restaurant)
• Fewer cells needed to cover a given area

Uniform Neighbors

Every hexagon has exactly 6 neighbors (except the rare pentagons). Squares have 8 neighbors (4 edges + 4 corners), but corner neighbors are farther away, complicating algorithms.

Hexagons provide geometric consistency that simplifies spatial algorithms and reduces edge cases.

What’s in This Series?

In this series, we’ll explore H3 in depth:

1. Hierarchical Structure: How H3’s multi-resolution hierarchy works, from icosahedron projection to 64-bit index encoding. Learn about resolution levels and parent-child relationships.

2. H3 Operations: Core API functions with practical code examples. Convert coordinates, traverse neighbors, fill polygons, and more.

3. Use Cases: Real-world applications from Uber, DoorDash, and epidemiology. Compare H3 with alternatives like Geohash and PostGIS.

4. Performance & Integration: Database integration patterns, performance characteristics, trade-offs, and best practices.

When to Use H3

H3 is the right choice when you need:

• ✅ Area-based analysis: Density maps, coverage regions, heatmaps
• ✅ Multi-resolution aggregation: Drill down from country → city → neighborhood
• ✅ Fast proximity queries: Find nearby points without expensive distance calculations
• ✅ Privacy-preserving location data: Coarse-grained cells instead of exact coordinates
• ✅ Uniform spatial partitioning: Consistent cell sizes for fair comparisons

H3 is not ideal for:

• ❌ Linear features: Roads, routes, pipelines (use specialized routing systems)
• ❌ Navigation: Turn-by-turn directions (use routing graphs)
• ❌ Sub-meter precision: Discretization error becomes significant
• ❌ Pure distance measurements: Use exact Haversine calculations

Conclusion

H3 transforms the messy problem of geospatial data into elegant, hierarchical indexing. By discretizing Earth into hexagonal cells, it makes location-based queries orders of magnitude faster while enabling new types of analysis.

Understanding H3 deepens your knowledge of:

• Spatial indexing and hierarchical data structures
• Trade-offs between exactness and performance
• How real-world systems like Uber and DoorDash operate at scale

Let’s start by exploring the Hierarchical Structure that makes H3’s multi-resolution magic possible.