VehicleMapping HD AV Spatial Data

Computing Content-Addressed Map Tile Deltas

A fleet cannot re-download a full HD map every time a single lane marking moves, so the HD map version control layer ships deltas — but a naive byte diff of two serialized tiles is almost the size of the tile itself, swamped by reordering and float re-encoding. This task computes a delta proportional to the semantic change by hashing canonicalized lane features into a content-addressed store, diffing the digest maps into add/modify/delete operations, and verifying the patched tile hashes back to the target. It is the mechanism behind small over-the-air updates and immutable, auditable map snapshots.

Two tile versions are hashed feature-by-feature; the digest diff yields a minimal add/modify/delete delta:

Content-Addressed Tile Delta Computation Base tile N and target tile N+1 each shown as a box of hashed features. An arrow from each leads to a central diff node producing three outputs: added, modified, deleted. These form a delta box. A final gate checks the patched base hashes to the target root digest. Base tile v N {id → digest} Target tile v N+1 {id → digest} digest diff set compare Delta + added ~ modified − deleted verify: apply(base, delta) root hash == target root hash

Prerequisites #

  • Python 3.10+, NumPy 1.24+, and the standard-library hashlib; Shapely 2.0+ for feature geometry.
  • Input: two tile snapshots, each a mapping of stable feature id → feature (lane boundary, centerline, regulatory element), in one projected CRS.
  • Upstream stage: features carry stable ids assigned at authoring time; geometry is already in the tile's committed coordinate reference system.
  • Output: a serialized delta plus a target root digest that a client can verify after patching.

Step-by-Step #

1. Canonicalize and hash each feature #

Determinism is the whole game: identical geometry must hash identically regardless of serialization order or float representation. Quantize coordinates to the positional tolerance, sort keys, and hash the canonical bytes.

python
import hashlib, json
import numpy as np

def canonical_bytes(feature: dict, grid_m: float = 1e-3) -> bytes:
    """Deterministic byte form: quantized coords + sorted keys."""
    f = dict(feature)
    coords = np.round(np.asarray(f["coords"], float) / grid_m) * grid_m
    f["coords"] = coords.tolist()
    return json.dumps(f, sort_keys=True, separators=(",", ":")).encode()

def feature_digest(feature: dict) -> str:
    return hashlib.sha256(canonical_bytes(feature)).hexdigest()

Key parameters: grid_m (1 mm) quantizes vertices so float re-encoding does not perturb the digest; sort_keys=True fixes attribute order. Expected output: a 64-hex-char digest that is stable across re-serialization.

2. Diff the digest maps #

Reduce each tile to an id→digest map, then set-compare. Added ids are in the target only, deleted in the base only, modified where the digest changed.

python
def diff_tiles(base: dict, target: dict) -> dict:
    """base, target: {feature_id: digest}. Returns an add/modify/delete delta."""
    added    = {k: target[k] for k in target.keys() - base.keys()}
    deleted  = [k for k in base.keys() - target.keys()]
    modified = {k: target[k] for k in base.keys() & target.keys()
                if base[k] != target[k]}
    return {"add": added, "modify": modified, "delete": deleted}

Key parameter: the maps hold digests, not full features — the diff is over hashes, so the comparison cost is independent of feature size. The full feature bytes for added/modified ids come from the content store keyed by digest.

3. Compute the tile root digest #

A tile's identity is a Merkle-style hash over its sorted feature digests. This root is what the client verifies against and what deduplicates whole tiles.

python
def tile_root(id_to_digest: dict) -> str:
    joined = "".join(f"{k}:{id_to_digest[k]}" for k in sorted(id_to_digest))
    return hashlib.sha256(joined.encode()).hexdigest()

Verification & Acceptance Criteria #

Never trust a delta you have not replayed. Apply it to the base and assert the reconstructed tile's root equals the target root.

python
def apply_delta(base: dict, delta: dict) -> dict:
    out = {k: v for k, v in base.items() if k not in set(delta["delete"])}
    out.update(delta["add"])
    out.update(delta["modify"])
    return out

def assert_delta_valid(base_map, target_map, delta):
    patched = apply_delta(base_map, delta)
    assert tile_root(patched) == tile_root(target_map), "patch != target root"
    print("delta verified: patched root matches target")

Acceptance gate: patched root digest equals target root; delta size scales with the number of changed features, not tile size; and every digest in add/modify resolves in the content store. Reject any delta whose replay diverges — a mismatch means a non-deterministic serialization leaked in.

Common Errors & Fixes #

Every feature shows as modified on an unchanged tile. The serialization is non-deterministic — dict order or float formatting varies. Route all hashing through canonical_bytes with sorted keys and quantized coordinates; never hash the raw serialized tile.

Delta is nearly the size of the tile for a one-lane edit. Coordinates are not quantized, so sub-tolerance float noise perturbs digests. Confirm grid_m matches the map's positional tolerance and is applied before hashing.

KeyError resolving a digest during patch apply. The content store was pruned of an object still referenced by an older delta. Treat stored objects as immutable and garbage-collect only digests unreachable from every retained root, the same immutability contract used for merging concurrent HD map edits.

Root matches but a client renders stale geometry. The client cached features by id, not digest, and reused an old body. Key the client cache by digest so a changed feature forces a fresh fetch.

FAQ #

Why hash features instead of diffing the raw tile bytes? #

A byte diff of a serialized tile is dominated by incidental reordering, floating-point re-encoding, and metadata churn, so a one-lane edit can produce a delta nearly as large as the whole tile. Hashing canonicalized features makes the delta proportional to the semantic change: reordering or re-serializing an unchanged lane yields the same digest and contributes nothing to the delta. That is what keeps over-the-air updates small.

What makes a feature serialization canonical? #

A canonical form fixes every degree of freedom that does not change meaning: sorted keys, a fixed coordinate precision, a fixed byte order, and vertices quantized to the map's positional tolerance. Two features that describe the same lane to within the tolerance must produce identical bytes, or they will hash differently and inflate the delta with phantom changes. Quantizing coordinates to a 0.001 m grid before hashing is the usual way to absorb float re-encoding noise.

How does this compare to storing a full copy per version? #

Content addressing deduplicates automatically: unchanged features across versions share one stored object keyed by digest, so N versions of a tile with small edits cost roughly one tile plus the deltas, not N tiles. It also makes integrity trivial — a tile's root digest is a Merkle hash over its feature digests, so a corrupted or tampered feature changes the root and is caught on load.

Up one level: HD Map Version Control — the parent workflow that turns these deltas into branchable, rollback-safe map snapshots.