Uber's Secret to Super-Fast Location Matching with H3

Part 2: How H3 Works Under the Hood

Before we dive into hexagonal grids and indexes, let’s start with the basic idea of what H3 does. Imagine you’re in a massive city, and Uber needs to find you a ride instantly. Instead of scanning a huge, chaotic list of driver coordinates, H3 breaks the world into smaller, manageable zones (hexagons). Each hexagon has a unique ID, and drivers are assigned to one of these hexagons based on their real-time location.

Think of it like a giant chessboard, except instead of squares, we use hexagons (because, as we’ll see, they’re just better). So, when you request a ride, Uber doesn’t have to look at every driver in the city—it just checks a few neighboring hexagons near you. This drastically reduces the complexity of searching and makes the system lightning fast.

How Does H3 Divide the World Into Hexagons?

H3 transforms the Earth's surface into a grid system, but not just any grid—a hierarchy of hexagons. Here’s how it works:

1. Start with an Icosahedron – Since Earth is a sphere (well, more like an oblate spheroid, but let’s not get picky), projecting a perfect hexagonal grid onto it is tricky. So, H3 first maps the Earth onto an icosahedron (a 20-sided shape made of triangles). You might ask, why 20 sides? Well, for starters, Earth's spherical shape is much closer to a 20-sided shape with equal triangular faces. This allows us to subdivide the triangular faces into hexagonal grids while maintaining a smooth and consistent tiling.
2. Subdivide into Hexagons – Each triangular face of the 20 equilateral triangle faces is split into smaller hexagonal cells, creating the base hexagonal grid.
3. Assign an H3 Index – Every hexagon gets a unique identifier (H3 Index), which encodes its location and resolution.

Understanding the H3 Index System

Each hexagon in H3 is labeled with a 64-bit index that encodes:

• Resolution Level – H3 supports multiple resolutions, meaning a hexagon can be further subdivided into smaller hexagons.
• Location Information – The index tells you exactly where that hexagon is on Earth.
• Parent-Child Relationships – A larger hexagon (parent) can be broken into smaller ones (children), maintaining a hierarchy for easy scaling.

This structure allows Uber to zoom in and out of locations efficiently. For example, a high-resolution hexagon (Resolution 15) may cover a single city block, while a lower-resolution hexagon (Resolution 0) could represent an entire continent. This hierarchical system allows Uber to adapt location precision based on the use case, ensuring efficient ride-matching at various levels of detail.

Visualizing H3 Mapping: From Sphere to Hexagons

In order to understand how H3 projects the Earth's spherical surface onto an icosahedron and then into hexagonal grids, I've provided an interactive Google Colab notebook. This visualization will:

• Show how an icosahedron is wrapped around a 3D sphere (representing Earth).
• Demonstrate how each triangular face is subdivided into hexagons at different resolutions.
• Illustrate how latitude/longitude coordinates are mapped onto hexagons at various precision levels.

Example: Resolution 2 Hexagonal Mapping
The image below shows H3 at Resolution 2, where the Earth's surface is mapped onto an icosahedron and subdivided into hexagons. At this level, the hexagons are large and provide a broad spatial representation before further refinement at higher resolutions.

👉 Check out the interactive visualization here (Google Colab link)

This will give a clear picture of how the H3 system works at different resolutions and why it is a powerful tool for spatial indexing.

Finding Nearby Hexagons with kRing / GridDisk

Now that we understand how the H3 index system works, the next step is determining which hexagons are adjacent to a given location—this is where the kRing (replaced by GridDisk) function comes in.

The kRing / GridDisk function helps find neighboring hexagons within a given radius. Instead of scanning an entire city to find nearby drivers, Uber can efficiently expand outward from a single hexagon to identify relevant areas.

How kRing Works

1. Start with a central hexagon – This is the rider’s location (converted into an H3 index).
2. Expand outward – The function finds all hexagons within k steps from the center.
   • k = 1 returns the 6 immediate neighbors.
   • k = 2 expands to 18 hexagons surrounding the center.
   • Larger k values cover a wider area.
3. Query for drivers in these hexagons – Instead of checking every driver in the city, Uber only looks at those inside these relevant hexagons.

This approach ensures that searches for nearby drivers are fast and scalable, avoiding unnecessary computations.

What’s Next?

Now that we understand how H3 structures the world into hexagons, in the next part, we’ll dive into practical implementation by writing a Go-based system using the H3 package to efficiently store and retrieve driver locations.

• How to implement H3 indexing in Golang using the h3-go package.
• Efficiently storing driver locations in Redis for real-time retrieval.
• Querying nearby drivers using spatial searches and optimizing performance.

Stay tuned for Part 3: Implementing H3 in Golang & Optimizing Driver Storage with Redis!