HD Map Version Control: Deterministic Spatial Pipelines for AV Fleets

HD map version control is the stage of the HD Mapping Architecture & Spatial Data Standards pipeline that turns validated road geometry into immutable, signed, atomically deployable tile sets — it sits after schema validation and immediately before edge distribution, and it must reconcile continuous multi-sensor ingestion, topological drift, and functional-safety gating while preserving sub-centimeter reproducibility across the fleet. The hard constraint is determinism: two ingests of the same scene must produce byte-identical version artifacts (≤0.1 mm coordinate quantization, identical Merkle roots), and any delta that introduces ≥0.05 m of centerline displacement or breaks lane connectivity must be rejected before it can reach a vehicle. Conventional Git collapses here because floating-point geometry is not line-diffable and binary tile payloads defeat text merge — versioning has to be graph-native, topology-aware, and cryptographically verifiable rather than a thin wrapper over a source-control tool.

Version control runs as a closed loop — fleet telemetry feeds the next ingestion cycle:

Versioning Models: Why a Spatial DAG, Not Git #

Before any code, fix the data model. The choice of versioning substrate determines whether deltas stay small, whether two ingests are reproducible, and whether a vehicle can verify a tile in milliseconds.

The spatial DAG is the only model that gives both per-primitive deltas and bit-exact reproducibility. Each road segment hashes to a stable Merkle root computed over canonically ordered, fixed-precision geometry, so an unchanged curb produces the same hash on every ingest and a single shifted lane boundary touches exactly one leaf. History is a directed acyclic graph of cryptographically signed spatial states, enabling per-region branching and cherry-pick of validated infrastructure changes — the same delta discipline the parent pipeline relies on for tile-level delta tracking and immutable snapshots.

Stage-by-Stage Implementation Walkthrough #

Multi-Sensor Ingestion & Temporal Alignment #

Constraint: inputs from LiDAR, camera-derived semantic masks, and GNSS/IMU must share a common time base to better than one IMU sample (≤2.5 ms at 400 Hz) before they can be fused into a single coordinate frame. Hardware PTP (IEEE 1588) timestamps remove inter-sensor skew; this is the same clock-domain alignment formalized upstream in LiDAR and camera temporal synchronization. The ingest buffer rejects multipath GNSS and dynamic-object noise (RANSAC plane fitting, Mahalanobis gating) and writes partitioned Apache Parquet keyed by spatial tile and temporal epoch, each row carrying acquisition metadata, per-feature confidence, and a provenance hash.

import pyarrow as pa
import pyarrow.parquet as pq
import numpy as np

def write_ingest_tile(features: dict, tile_id: str, epoch: int, out_dir: str) -> str:
    # features: dict of equal-length numpy arrays (x, y, z, kind, confidence)
    table = pa.table({
        "x": features["x"].astype(np.float64),
        "y": features["y"].astype(np.float64),
        "z": features["z"].astype(np.float64),
        "kind": features["kind"],                       # lane | curb | sign | crosswalk
        "confidence": features["confidence"].astype(np.float32),
        "provenance": features["provenance"],           # per-feature source hash
    })
    path = f"{out_dir}/tile={tile_id}/epoch={epoch}/part.parquet"
    pq.write_table(table, path, compression="zstd")     # partition by tile + epoch
    return path

Partitioning by tile and epoch keeps per-worker memory bounded and lets the rest of the pipeline parallelize without loading a whole region into RAM.

Spatial Normalization & Datum Enforcement #

Constraint: every feature must land in one metric frame with ≤0.5 cm transformation residual against surveyed control points, or downstream topology drifts. Heterogeneous source datums are projected into a local tangent plane (or ECEF) with pyproj, and the exact transform — matrix, epoch, projection parameters — is serialized as immutable metadata so any consumer can reconstruct the coordinate context during replay or simulation. This is the projection-chaining discipline covered in depth for coordinate reference systems for AVs; batches whose control-point residual exceeds 0.5 cm are quarantined for surveyor review rather than versioned.

import numpy as np
from pyproj import Transformer

def normalize_to_local(lon, lat, alt, src_epsg: int, dst_epsg: int):
    tf = Transformer.from_crs(src_epsg, dst_epsg, always_xy=True)
    x, y = tf.transform(lon, lat)
    meta = {"src_epsg": src_epsg, "dst_epsg": dst_epsg,
            "pipeline": tf.description}               # immutable, attached to tile
    return np.column_stack([x, y, alt]), meta

def assert_datum_residual(measured, control, tol_m: float = 0.005):
    res = np.linalg.norm(measured - control, axis=1)
    if res.max() > tol_m:                              # ≤0.5 cm gate
        raise ValueError(f"datum residual {res.max()*100:.2f} cm > {tol_m*100} cm")

Topological Validation & Schema Compliance #

Constraint: only structurally valid road networks enter the version graph. Normalized features are parsed against the target exchange schema and checked for reference-line continuity, junction validity, and connectivity — the linter maps one-to-one onto the rules in the OpenDRIVE schema breakdown and the connectivity model in lane-level topology modeling. Graph traversal verifies the lane connectivity matrix and flags orphaned segments, invalid junctions, and missing regulatory elements; only artifacts that pass advance to staging. Formal validation against the ASAM OpenDRIVE specification preserves interoperability with third-party simulation and localization stacks.

import networkx as nx

def validate_topology(edges, nodes) -> list[str]:
    g = nx.DiGraph()
    g.add_nodes_from(nodes)
    g.add_edges_from(edges)                            # (pred_lane, succ_lane)
    errors = []
    orphans = [n for n in g.nodes if g.degree(n) == 0]
    if orphans:
        errors.append(f"{len(orphans)} orphaned lane segments")
    for junction, succs in ((n, list(g.successors(n))) for n in g.nodes):
        if g.out_degree(junction) and not succs:      # phantom connection
            errors.append(f"junction {junction} declares exits with no successor")
    return errors                                     # empty list == promotable

Deterministic Diffing & Graph-Based Versioning #

Constraint: the diff must be a pure function of geometry and topology, independent of float formatting or feature ordering. Coordinates are quantized to a fixed grid (1e-6° geographic, or 0.1 mm in the local frame), edge lists are sorted into canonical vertex order, and each segment hashes to a stable Merkle root. Only changed primitives propagate; a spatial edit-distance metric quantifies topological divergence so an update that introduces a localization discontinuity can be rejected before signing.

import hashlib
import numpy as np

def segment_hash(coords: np.ndarray, attrs: bytes, q_m: float = 1e-4) -> str:
    # quantize to a 0.1 mm grid so float noise can't change the hash
    grid = np.round(coords / q_m).astype(np.int64)
    # canonical ordering: lexicographic on quantized vertices
    order = np.lexsort(grid.T[::-1])
    payload = grid[order].tobytes() + attrs
    return hashlib.sha256(payload).hexdigest()         # stable Merkle leaf

def changed_segments(prev: dict[str, str], curr: dict[str, str]) -> set[str]:
    # prev/curr: segment_id -> segment_hash
    return {sid for sid in curr if prev.get(sid) != curr[sid]}

Release Orchestration & Fleet Synchronization #

Constraint: rollouts must be atomic and reversible. Each tile is signed and packaged with a manifest carrying its dependency graph, localization fallback parameters, and rollback triggers. Vehicles verify incoming deltas against current state with a lightweight client that checks hash consistency and topological continuity; a delta that degrades localization confidence or violates kinematic limits triggers automatic revert to the last known-good version. This closed-loop gate keeps spatial updates deterministic across heterogeneous platforms and satisfies ISO 26262 requirements for over-the-air software updates. Telemetry from deployed vehicles feeds the next ingestion cycle, closing the loop between real-world perception and map version control.

def verify_delta(local_root: str, delta_manifest: dict) -> bool:
    if delta_manifest["base_root"] != local_root:      # wrong ancestor
        return False
    for seg_id, expected in delta_manifest["segment_hashes"].items():
        if not signature_valid(seg_id, expected, delta_manifest["sig"]):
            return False
    return delta_manifest["max_centerline_shift_m"] <= 0.05   # safety envelope

Validation & QC Automation #

Every promotion is gated by deterministic checks wired into CI so no human judgment is in the merge path:

• Datum residual ≤ 0.5 cm against surveyed control points (hard quarantine above threshold).
• Centerline displacement ≤ 0.05 m between consecutive versions of an unchanged segment; larger shifts must be explained by an upstream change set or are rejected.
• Lane connectivity — zero orphaned segments, zero phantom successors, zero invalid junctions in the directed lane graph.
• Self-intersection count = 0 on every lane boundary and curb polyline (shapely is_simple).
• Hash reproducibility — re-ingesting the same source Parquet must reproduce identical Merkle roots; a CI job ingests a frozen fixture twice and asserts root equality.

from shapely.geometry import LineString

def qc_segment(coords, prev_coords=None) -> list[str]:
    issues = []
    line = LineString(coords)
    if not line.is_simple:
        issues.append("self-intersecting boundary")
    if prev_coords is not None:
        shift = LineString(prev_coords).hausdorff_distance(line)
        if shift > 0.05:                               # ≤0.05 m centerline gate
            issues.append(f"centerline shift {shift:.3f} m > 0.05 m")
    return issues

A failing check blocks the merge and writes the offending segment ids to the CI log so the regression is localized to a tile rather than a region.

Edge Cases & Failure Patterns #

• Quantization seam at tile borders. A vertex on a tile boundary can quantize differently in adjacent tiles, producing two hashes for one curb and a false delta. Snap shared boundary vertices to a single global grid before hashing.
• Float reordering on re-serialization. Writing geometry through different pyproj/shapely versions can reorder rings or flip winding; without canonical ordering this changes the hash. Enforce lexsort + fixed winding before segment_hash.
• XSD namespace drift across OpenDRIVE versions. A tile authored against OpenDRIVE 1.7 validated against a 1.8 schema fails on renamed elements. Pin the schema version per branch and validate against the version recorded in the tile manifest.
• PTP holdover during GNSS outage. When the clock disciplines drift in a tunnel, ingest timestamps skew and temporal alignment silently degrades. Flag epochs whose PTP offset exceeds 2.5 ms and quarantine rather than fuse them.
• Rollback into a pruned ancestor. A vehicle whose last known-good root has been garbage-collected cannot verify the base_root. Retain signed snapshots for the full fleet refresh window before pruning the DAG.

Performance & Scale Notes #

Region-scale ingests routinely exceed single-host RAM, so the pipeline is built around bounded memory rather than whole-region loads:

• Memory-mapped reads. Access Parquet partitions through Arrow zero-copy buffers (or numpy.memmap for raw point clouds) so working set stays at the tile granularity, not the region.
• Tile-parallel workers. Hash and validate one tile/epoch partition per worker; the spatial DAG merge is associative, so per-tile Merkle roots combine without cross-worker locking.
• Delta-only propagation. Because only changed_segments ship downstream, OTA payloads scale with the edited geometry, not the map — a single curb edit is kilobytes, not the megabyte tile.
• Content-addressed dedup. Identical segment hashes across versions and regions share one stored blob, collapsing storage for the large unchanged remainder of the map.
• Streaming verification on the vehicle. The verify client checks hashes incrementally as the delta arrives, keeping peak memory at one segment and aborting early on the first mismatch.

Frequently Asked Questions #

Why can't I just version HD maps in Git or Git-LFS? Floating-point geometry is not line-diffable: re-serialization reorders rings, flips winding, and reformats floats, so a textual diff reports a whole-feature rewrite for a single shifted vertex. Git-LFS treats each tile as an opaque blob and offers no semantic delta. A topology-aware spatial DAG hashes canonically ordered, fixed-point geometry so an unchanged curb yields the same Merkle leaf on every ingest and one edited lane touches exactly one leaf.

How do two ingests of the same scene stay byte-identical? Quantize every coordinate to a fixed grid (0.1 mm in the local frame, 1e-6° geographic), sort vertices into canonical lexicographic order, and hash with SHA-256. Quantization absorbs float noise below the grid step and canonical ordering removes serialization-order variance, so the Merkle root is a pure function of geometry and topology — re-ingesting the same source Parquet reproduces identical roots, which a CI fixture asserts on every build.

What stops a bad update from reaching a vehicle? Every promotion passes deterministic CI gates with no human in the merge path: ≤0.5 cm datum residual against control points, ≤0.05 m centerline displacement on unchanged segments, zero orphaned segments or phantom successors in the lane graph, zero self-intersections, and reproducible hashes. On the vehicle, the verify client checks the delta's base_root, per-segment signatures, and the ≤0.05 m safety envelope before applying it, and auto-reverts to the last known-good version if localization confidence degrades — satisfying ISO 26262 over-the-air update requirements.

How large is the over-the-air payload for a small edit? Only changed primitives propagate, so a payload scales with the edited geometry rather than the map: a single repainted curb is kilobytes, not the megabyte-scale tile. Content-addressed deduplication means identical segment hashes across versions and regions share one stored blob, collapsing storage for the large unchanged remainder.

Related #

• Coordinate Reference Systems for AVs — the datum governance and projection chaining that feeds the normalization stage.
• OpenDRIVE Schema Breakdown — the structural rules the topological validation gate enforces before versioning.
• Lane-Level Topology Modeling — predecessor/successor graph construction underpinning the connectivity checks.
• LiDAR and Camera Temporal Synchronization — the clock-domain alignment that the ingestion stage depends on.
• Point Cloud Registration with the ICP Algorithm in Python — upstream registration whose output becomes versioned tile geometry.

This page is part of the HD Mapping Architecture & Spatial Data Standards reference; return there for the end-to-end pipeline and its sibling stages.