Maps and Proximity Search

Scope

This design covers static points of interest (POIs), versioned vector tiles, and traffic-aware road routing. It deliberately does not claim to be a moving-driver or real-time fleet index. Those systems need a different update-rate, staleness, privacy and assignment model.

H3 is used only to generate candidates. It is not an exact distance function and its cells are not equal-area. The authoritative inclusion predicate is an exact geospatial calculation in the POI store.

Correctness invariants

1. Latitude is in [-90, 90], longitude is normalized consistently, radius/result count/filter complexity are bounded, and malformed numbers fail closed.
2. Candidate generation has no false negatives within the supported query envelope. Its boundary margin and fan-out cap are tested at ordinary cells, all pentagons, high latitudes and the antimeridian.
3. Every candidate is hydrated from current authoritative state and checked by an exact distance predicate before it is returned.
4. A cache stores candidate ids/attributes by covered cells, filters and catalog generation. It never reuses a final distance ordering for every point inside a cell.
5. POI state and an outbox event commit together. The indexer applies monotonic versions, removes an old-cell entry on movement, and preserves tombstones.
6. Ranking has a documented direction for every normalized feature and a stable final POI-id tie-break. A cursor pins the query and index/catalog generation.
7. A routing request uses one compatible graph and metric snapshot. Traffic weights participate in route selection, not only in a post-hoc ETA label.
8. Tiles are immutable by data/style version and still addressed separately by z/x/y at each zoom.

[CASE]search-engine

Why a fixed H3 ring is wrong

The H3 resolution table reports that resolution 9 has average cell area about 0.1053 km², but minimum and maximum hexagon areas differ materially. H3 has twelve pentagons at every resolution, and grid traversal APIs document distortion behavior around them. Therefore “resolution 9, k = 1 covers 2 km” is not a valid geometric guarantee.

In an undistorted hex neighborhood, gridDisk has at most 1 + 3k(k + 1) cells. That counts graph cells; it does not turn k into a universal radius in meters. The implementation instead builds a conservative cover of the query circle at the configured resolution, adds a validated boundary margin, and rejects a request that exceeds the fan-out budget. Exact geography distance then decides inclusion.

For PostGIS geography, ST_DWithin takes distance in meters and can use an index bounding-box prefilter. The final distance model (spheroid or documented sphere approximation) is consistent between filtering, ranking and the response.

Query flow

1. Normalize and validate coordinates, radius, filters, result limit and cursor.
2. Resolve a conservative set of index cells. Retrieve candidate ids from a cache keyed by cell set/filter/catalog generation, or the H3 projection on a miss.
3. Fetch current POIs and apply ST_DWithin. Deleted, stale-version and policy-ineligible rows disappear here.
4. Calculate exact per-request distance and normalized rank. Distance contributes negatively, for example score = quality − lambda × normalized_distance, with POI id as the last tie-break.
5. Return a cursor that binds normalized query, last score/distance/id, and catalog/index generation. If the generation is no longer retained, restart explicitly rather than silently skip or duplicate rows.

A query centered elsewhere in the same H3 cell gets a new exact ordering. Candidate caching remains useful without asserting that the cell center equals the user.

[CONCEPT]partitioning-strategies

Catalog update and index convergence

The catalog service writes current POI state and an outbox row in one transaction. Each event includes POI id, source version, prior cell (or enough state to resolve it), new cell and tombstone flag. The projector:

• ignores duplicate or lower versions;
• deletes the prior cell membership when a POI moves;
• applies the new membership or tombstone;
• advances a catalog generation only after a complete projection checkpoint;
• expires candidate-cache generations rather than attempting unreliable wildcard deletion.

This is eventually consistent discovery with source-of-truth verification. An administrative read-after-write endpoint can read the authoritative row and expose projection lag; ordinary search may lag but cannot return a deleted/moved POI after the final hydration check.

Vector tiles

Mapbox Vector Tile is a protobuf format for tiled vector data. It does not eliminate the zoom pyramid: clients still request z/x/y, and features are clipped/quantized into each tile's coordinate system. Generalization, attributes, geometry complexity and compression determine size, so the diagram makes no universal “20× smaller” claim.

The cache key includes style version, data version and z/x/y. A deployment can precompute popular zooms and render colder tiles on demand, but it publishes immutable versions and prevents a tile from mixing a style with an incompatible schema. The CDN can keep old versions until active clients age out.

Traffic-aware routing

The flow follows the public OSRM distinction between Contraction Hierarchies (CH) and Multi-Level Dijkstra (MLD). OSRM documents that osrm-customize can repeatedly apply segment-speed and turn-penalty updates to a partitioned MLD graph. The design therefore publishes a complete metric snapshot tied to a graph version.

A route worker pins graph and metric versions for the whole request. If a new metric is incomplete or incompatible, it serves the last complete version with freshness metadata or fails according to product policy. It does not calculate a static path and then pretend that changing only its ETA made the path traffic-optimal.

Traffic updates must be validated for impossible speeds, direction, turn identity, source quality and age. Route alternatives and snapping radii are bounded to control worst-case work.

Antimeridian, poles and distortion

Longitude arithmetic cannot assume a flat interval around ±180°. GeoJSON guidance recommends cutting geometries that cross the antimeridian; an implementation can normalize/split its cover geometry or use a geospatial library whose spherical behavior is explicitly tested. Near poles and H3 pentagons, traversal errors or abnormal fan-out trigger the conservative fallback and budget, never a smaller unchecked candidate set.

Capacity model

All values are deployment inputs, not facts about a global map service:

• cell lookups per request = number of cells in conservative cover;
• candidate bytes per second = QPS × candidate ids per cover × encoded bytes, reduced by generation-cache hits;
• exact-check work = QPS × candidates after cheap attribute filters;
• index update rate = POI changes per second, with movement causing old-cell delete plus new-cell insert;
• tile egress = tile requests per second × observed compressed tile bytes × CDN miss ratio;
• route CPU = route requests per second × measured graph-search cost for the selected algorithm/profile;
• traffic customization objective = complete metric build time plus publication time, not raw event arrival latency.

Measure distributions by latitude, radius, city density, filter, zoom and route distance. Averages conceal dense-city fan-out and long-route tails.

Failure and abuse model

• Cache outage falls back to the bounded H3 index and still performs exact checks; limits may tighten under load.
• Index lag is surfaced and final hydration prevents ghosts. If source-of-truth capacity is unavailable, fail or serve an explicitly stale product mode; do not call cached candidates exact.
• Poison catalog events enter quarantine while later independent POIs can progress; a per-POI version gap is visible and replayable.
• Metric publication is atomic. A partially customized graph is never routable.
• Tile origin failure can serve an older immutable compatible version under declared staleness policy.
• Query rate, radius, result count and distinct-filter cardinality are limited to prevent spatial fan-out abuse.
• Precise user coordinates are sensitive. Logs and analytics minimize/quantize them under a documented retention and access policy.

References

• H3: Tables of cell statistics across resolutions — official average/min/max cell areas and pentagon counts.
• H3: Grid traversal functions — official gridDisk behavior and pentagon distortion caveats.
• H3 documentation — hierarchy and approximate geometric containment context.
• PostGIS: ST_DWithin — geography distances in meters and index-assisted prefiltering.
• Mapbox Vector Tile Specification 2.1 — primary z/x/y vector-tile format and coordinate model.
• Project OSRM: tools — official CH/MLD pipeline and repeated MLD traffic customization.
• Project OSRM: backend — official routing-engine algorithm guidance.
• RFC 7946, section 3.1.9 — antimeridian geometry guidance.

Interactive scenarios

▶Walkthrough: nearby (not found) ▶Walkthrough: distorted-grid (not found) ▶Walkthrough: catalog-update (not found) ▶Walkthrough: vector-tile (not found) ▶Walkthrough: traffic-route (not found) ▶Walkthrough: cache-failure (not found)