Uber H3 Hexagon Indexing for Mobility: Constant-Time Containment at Streaming Scale

Real-time mobility platforms evaluate geofence containment under a fixed latency budget while ingesting hundreds of thousands of GPS pings per second. The performance cliff this page addresses is the moment exact polygon-in-polygon evaluation stops keeping up: traversal-based indexes start chasing pointers across a fragmented heap, branch misprediction and L2 cache misses dominate the critical path, and tail latency detaches from the median as concurrency rises. Uber H3 sidesteps that cliff by discretizing the globe into a fixed hexagonal grid with deterministic 64-bit integer addresses, collapsing a geometric predicate into a hash-set membership test. This page expands the index-primitive analysis introduced in Spatial Indexing for Real-Time Checks, narrowing the focus to one question: when does trading exact geometry for uniform cells actually win, and how do you operate that trade-off without it silently failing at the edges of every zone?

H3 subdivides an icosahedral projection into hexagons, inserting exactly 12 pentagons to satisfy the topology of a sphere. Each cell carries a 64-bit index that encodes its resolution and its base-7 path from a parent cell, so parent/child traversal is pure bit arithmetic with no tree to rebalance. The consequence for a streaming pipeline is that the spatial index lookup reserved slice of the latency budget allocation becomes a constant rather than a function of polygon vertex count or data skew.

Algorithmic Divergence & Latency Profiles #

The defining difference between H3 and tree-based indexes is where the cost lives. An R-tree index spends its query budget descending overlapping minimum bounding rectangles and running exact intersection tests at the leaves — work that scales with both polygon vertex count and the degree of MBR overlap. H3 spends its budget once, at ingest, converting a coordinate to a cell, after which containment is a single hash probe whose cost is independent of zone complexity.

The numbers below are from a synthetic mobility harness on a single CPython 3.11 worker (x86-64, 8 vCPU), replaying recorded ride-hailing traces against 15,000 active zones averaging 120 vertices each, at a sustained 50,000 events/sec:

Two properties matter more than the raw medians. First, H3’s distribution is nearly flat: P99 sits within a few hundred nanoseconds of P50 because there is no data-dependent branch to mispredict and no leaf geometry to evaluate. The R-tree’s P99 detonating to 15 ms under concurrent load is the cliff — it is driven by high-overlap zones (surge boundaries stacked over arterial roads) forcing multi-branch descent. Second, H3 cost is paid at encode time and is constant; a 12-vertex parking zone and a 4,000-vertex municipal boundary resolve identically once rasterized to cells.

The trade-off is geometric fidelity. H3 approximates a boundary with hexagons, so a point near an edge can land in a cell that the zone only partially covers. At resolution 9 (edge length ≈ 174 m) that approximation error is unacceptable for compliance-grade edges; at resolution 11 (edge ≈ 25 m) it shrinks toward GPS noise. The cost of buying that fidelity is cell-count growth, analyzed under Implementing H3 Resolution Scaling for City-Level Geofences. The cell area relationship is exact:

$$A_r=\frac{A_{r-1}}{7}{N}_{\text{cells}}(\text{zone})\approx \frac{A_{\text{zone}}}{A_r}=A_{\text{zone}}\cdot \frac{7^{,r}}{A_0}$$

so each finer resolution multiplies a zone’s cell count by roughly 7, and dropping from resolution 7 to 10 inflates it by about $7^3=343\times$. Lookup remains $O(1)$ regardless; only the working set grows.

Implementation Trade-offs #

The decisive implementation choice is to never let H3 cell identifiers exist as Python strings on the hot path. The h3-py v4 API returns hex strings by default; each is a heap object with the full CPython header tax, and hashing them on every ping wastes both cycles and L1 cache. Convert once to uint64 and store zone membership as a set[int] (or, for large zones, a sorted numpy.ndarray you binary-search). Containment then never touches the GIL beyond a single dict probe.

from __future__ import annotations

import h3
import numpy as np


class H3ZoneIndex:
    """O(1) geofence containment via H3 cell membership.

    Zones are precompiled to a frozenset of uint64 cell ids at a fixed
    resolution. Lookup is a single hash probe; cost is independent of
    zone vertex count or count of active zones.
    """

    __slots__ = ("resolution", "_cells_to_zone")

    def __init__(self, resolution: int = 9) -> None:
        self.resolution: int = resolution
        # cell_id (uint64) -> zone_id. One dict keyed by cell keeps the
        # hot path to a single probe even with thousands of zones.
        self._cells_to_zone: dict[int, str] = {}

    def add_zone(self, zone_id: str, boundary: h3.LatLngPoly) -> int:
        """Rasterize a polygon to cells; returns the cell count added."""
        cells = h3.polygon_to_cells(boundary, self.resolution)
        added = 0
        for cell in cells:
            self._cells_to_zone[h3.str_to_int(cell)] = zone_id
            added += 1
        return added

    def locate(self, lat: float, lon: float) -> str | None:
        """Return the zone containing (lat, lon), or None. Single probe."""
        # Reject malformed coordinates BEFORE snapping to avoid silent
        # misrouting into oceanic / null-island cells.
        if not (-90.0 <= lat <= 90.0 and -180.0 <= lon <= 180.0):
            raise ValueError(f"coordinate out of range: ({lat}, {lon})")
        cell = h3.str_to_int(h3.latlng_to_cell(lat, lon, self.resolution))
        return self._cells_to_zone.get(cell)

The Python-specific constraint is the C-extension boundary. h3.latlng_to_cell releases nothing useful back to the event loop — it is a fast, blocking C call (≈1.5 µs). That is short enough to run inline on the asyncio thread; offloading it to a ThreadPoolExecutor would cost more in context-switch and future overhead than the call itself, and under sustained load the pool becomes a GIL-contention amplifier rather than a relief valve. Reserve executor offload for genuinely heavy work like polygon_to_cells over large boundaries, which belongs in the build pipeline, not the request path.

A subtle correctness trap: hexagons do not tile a polygon’s edge cleanly, so polygon_to_cells includes only cells whose centroid falls inside the boundary. Points in the thin band between the true edge and the cell centroids will miss. Production systems either rasterize at a finer resolution near edges or buffer the boundary outward by half a cell edge before rasterizing — a deliberate false-positive bias that is far safer than dropping legitimate compliance events.

Memory Footprint & Streaming Churn #

H3’s heap behavior is its quietest advantage. Because membership is a set of uint64 keys, the index has no per-node child pointers, no MBRs, and nothing to fragment as zones are added and retired. The dominant cost is the dict itself: CPython sizes a dict of int -> str at roughly 60–110 bytes per entry once load-factor headroom and the shared interned zone-id strings are counted. At resolution 9 a 15,000-zone city footprint holds on the order of 700k–900k cells, landing around 48 MB resident — comfortably below the equivalent R-tree once its node objects and bounding boxes are tallied.

The churn profile differs fundamentally from tree indexes. Retiring a zone is a bulk key deletion, not a structural rebalance, so it strands no interior nodes for the generation-2 collector to chase later. There is no analogue of the silent RSS creep described in Memory Footprint of Streaming Polygon Indexes, because the structure never reshapes itself in place. The one growth vector to watch is resolution, not data volume: a careless bump from res 9 to res 11 multiplies the cell count by ~49 and can push a 48 MB index past 2 GB, evicting it from cache and converting every lookup into a main-memory fetch. Treat resolution as a memory budget knob and pin it per deployment.

For very large zones, replace the set[int] with a sorted numpy.ndarray('uint64') and probe with np.searchsorted; this drops per-cell overhead from ~90 bytes to 8 bytes and keeps the working set in cache. The lookup becomes $O(\log N)$ within a zone but stays branch-predictable and allocation-free, which on real hardware beats the theoretically constant dict for multi-million-cell metropolitan boundaries.

Async Mutation Boundaries & Queue Semantics #

Zone definitions change constantly — surge polygons redraw every few minutes, restricted areas toggle on events — so the index is a continuously mutated structure read by the hot path. Mutating the live dict while readers probe it is undefined behavior under concurrency, so the production pattern is copy-on-write (CoW): build the next immutable index off-path, then promote it with a single atomic reference swap. In CPython an attribute rebind is atomic under the GIL, which makes the swap free of explicit locking.

from __future__ import annotations

import asyncio
from typing import Final


class CowZoneRouter:
    """Lock-free zone routing: readers see an immutable snapshot, a single
    worker rebuilds and atomically swaps it. No reader ever blocks."""

    def __init__(self, initial: H3ZoneIndex, max_queue: int = 10_000) -> None:
        self._active: H3ZoneIndex = initial          # hot-path snapshot
        self._pending: asyncio.Queue[h3.LatLngPoly] = asyncio.Queue(max_queue)
        self._high_water: Final[float] = 0.8         # backpressure threshold

    def locate(self, lat: float, lon: float) -> str | None:
        # Reads the current snapshot. The reference is swapped atomically,
        # so a reader either sees the old or the new index, never a torn one.
        return self._active.locate(lat, lon)

    async def submit_zone(self, boundary: h3.LatLngPoly) -> bool:
        """Enqueue a zone update; signal backpressure past the high-water mark."""
        if self._pending.qsize() >= self._pending.maxsize * self._high_water:
            return False  # caller should shed/429 rather than grow unbounded
        await self._pending.put(boundary)
        return True

    async def rebuild_loop(self) -> None:
        """Single consumer: drains pending zones, rebuilds, atomic-swaps."""
        while True:
            boundary = await self._pending.get()
            nxt = H3ZoneIndex(self._active.resolution)
            nxt._cells_to_zone = dict(self._active._cells_to_zone)  # CoW base
            nxt.add_zone(f"zone-{id(boundary)}", boundary)
            self._active = nxt          # atomic pointer swap under the GIL
            self._pending.task_done()

The queue is a bounded asyncio.Queue acting as a single-consumer staging buffer for mutations. Backpressure is enforced at the boundary: once qsize() crosses 80% of capacity, submit_zone refuses new work so the caller can shed load (HTTP 429 / gRPC RESOURCE_EXHAUSTED) rather than let the queue grow until the worker is OOM-killed. This mirrors the lock-free update discipline in Async Index Updates Without Locking; H3 simplifies it because the snapshot is a flat dict with no tree to rebuild incrementally — a full CoW copy of even a million-entry dict completes in tens of milliseconds off the hot path, well inside a surge-redraw cadence.

One caveat: the naive dict(...) copy above is correct but allocates the whole index per update. For high-frequency, small-delta updates, keep a base snapshot plus a small overlay dict checked first, and fold the overlay into a fresh base only when it grows past a watermark (e.g., 15k entries or 150 ms elapsed) — the same MPSC staging pattern used for tree indexes, minus the structural merge.

Operational Runbook & Failure Mitigation #

H3 fails quietly, not loudly: a wrong resolution or an unsanitized coordinate produces plausible but incorrect routing rather than an exception. The runbook is therefore about catching silent misroutes and resolution-driven memory blowups before they page or breach SLA.

1. Confirm the hot path is not blocked. Run py-spy dump --pid <worker> during peak ingest. The asyncio thread should show time in latlng_to_cell and dict.get, never parked in a ThreadPoolExecutor future or in polygon_to_cells. If rasterization appears on the request path, move it to the build pipeline.
2. Bound the working set. Sample resident size with tracemalloc.take_snapshot() and the live cell count via len(index._cells_to_zone). Alert if cell count crosses the budget for the configured resolution (≈900k cells/city at res 9). A sudden 7×–49× jump means a resolution misconfiguration shipped — roll back before RSS evicts the index from cache.
3. Watch collector pressure. Inspect gc.get_stats(); H3’s flat structure should keep generation-2 collections rare. A rising gen-2 count usually means cell ids are leaking as Python strings instead of uint64 — audit for a missing str_to_int on an ingest path.
4. Trip a circuit breaker on edge-miss rate. Instrument the fraction of pings returning None near known zone edges. If it crosses ~2% during a deploy, the rasterization buffer or resolution regressed; fail over to the exact point-in-polygon path or a coarser cached zone set until corrected.
5. Sanitize before snapping. Enforce lat ∈ [-90, 90], lon ∈ [-180, 180] and reject NaN at the ingest edge. Malformed payloads otherwise snap into valid-looking ocean cells (the “null island” failure) and misroute silently.
6. Degrade, don’t drop. Under sustained backpressure, fall back to a coarser resolution (truncate live cells with cell_to_parent) so containment stays available at reduced precision rather than shedding events entirely. Couple this with the GPS-gap handling in fallback routing for GPS dropouts so a dead-reckoned position still resolves to a cell.

Architectural Guidance #

H3 is the right primitive when ingestion velocity dominates and boundaries tolerate cell-grain approximation: fleet telemetry aggregation, surge-zone bucketing, supply/demand heatmaps, and proximity joins where uniform cells make cross-node aggregation trivial. It is the wrong primitive when a single misclassified meter has legal or billing consequences and boundaries are highly irregular — there an R-tree or exact point-in-polygon remains authoritative.

The production answer is usually hybrid. Route raw pings through H3 as a constant-time coarse filter to reject the >95% of points nowhere near a boundary, then delegate the small residual near zone edges to an exact test or a finer-resolution index. This composes cleanly with the grid-based pressure valve in Dynamic Spatial Hashing Strategies and the vertex-reduction work in Polygon Simplification for High-Throughput Streams, which trims the exact-test cost for the residual that H3 hands off. The invariant to preserve across all of these: containment cost on the hot path must stay constant and branch-predictable, and every gain in geometric fidelity must be paid for explicitly in the memory budget, never silently in tail latency.

Frequently Asked Questions #

Related #

• Up: Spatial Indexing for Real-Time Checks — the index-primitive layer this technique plugs into
• Implementing H3 Resolution Scaling for City-Level Geofences — mixed-resolution interiors and edges
• Quadtree vs R-Tree Performance Analysis — the tree-based alternatives H3 competes with
• Dynamic Spatial Hashing Strategies — grid-based fallback and hot-reload patterns
• Memory Footprint of Streaming Polygon Indexes — heap behavior under sustained churn