VehicleMapping HD AV Spatial Data

Producing ISO 26262 Traceability for Map Artefacts

Traceability sounds like a documentation task and is really a data-modelling one. The question an investigation asks is narrow and specific — this lane, on this date, where did it come from — and a system that can only answer it at release granularity cannot answer it at all. The question a change asks is the mirror image: this survey pass was wrong, what does that invalidate.

Both are answerable cheaply if provenance is keyed by content digest and every input is immutable, and expensively or not at all otherwise. This task builds that for HD map quality assurance and certification, on top of the digests computing content-addressed map tile deltas already produces.

The two queries the record has to serve, running in opposite directions over the same graph:

The Forward Query and the Impact Query Over One Provenance Graph A layered graph from inputs through feature digests to releases, annotated with a right-to-left forward query and a left-to-right impact query. survey pass 7f3a… toolchain c19b… validation run 42 feature 9f2c… feature 4b81… tile 12021… release 2026-32 forward query: this lane → its survey pass, operator, toolchain impact query: this pass was faulty → every shipped feature needing re-verification

Prerequisites #

  • Python 3.10+, pyarrow 14+ for the columnar provenance sidecar.
  • Input: features carrying content digests, plus immutable references for survey passes, toolchain builds and validation runs.
  • Upstream stage: the digesting step in version control; provenance is written alongside features, not derived afterwards.
  • Output: a provenance table keyed by feature digest, and two query functions over it.

Step-by-Step #

1. Write the record keyed by feature digest #

The record is small and flat, and every field it references is itself content-addressed.

python
from dataclasses import dataclass

@dataclass(frozen=True, slots=True)
class Provenance:
    feature_digest: str      # what this record describes
    survey_pass: str         # digest of the immutable capture bundle
    captured_iso: str        # capture time, not ingest time
    operator: str            # crew or automated pipeline identifier
    toolchain: str           # digest of the build image + config
    validation_run: str      # identifier of the run that verified it

def record_for(feature, build) -> Provenance:
    return Provenance(
        feature_digest=feature.digest,
        survey_pass=feature.source.pass_digest,
        captured_iso=feature.source.captured_iso,
        operator=feature.source.operator,
        toolchain=build.toolchain_digest,
        validation_run=build.validation_run_id,
    )

Note what is not here: a file path, a bucket name, a ticket number. Those name things that move, and a record that resolves to whatever a path holds today is not evidence about the build. Expected output: one immutable record per distinct feature version.

2. Store it columnar, deduplicated by digest #

An unchanged lane produces the same digest across releases, so it needs one record no matter how many releases ship it.

python
import pyarrow as pa
import pyarrow.parquet as pq

def append_provenance(path, records: list[Provenance], existing: set[str]) -> int:
    """Write only records whose feature digest is not already stored."""
    fresh = [r for r in records if r.feature_digest not in existing]
    if not fresh:
        return 0
    table = pa.Table.from_pylist([r.__dict__ for r in fresh])
    pq.write_to_dataset(table, root_path=path, partition_cols=["survey_pass"])
    return len(fresh)

Partitioning by survey_pass is what makes the impact query cheap: invalidating a pass is a partition scan rather than a full-table filter. Expected output: the count of genuinely new records, which on a typical release is a small fraction of the map.

3. Derive the impact set #

python
def impact_set(provenance_root, bad_pass_digest: str,
               shipped_digests: set[str]) -> set[str]:
    """Shipped feature digests whose provenance names a suspect survey pass."""
    tbl = pq.read_table(provenance_root,
                        filters=[("survey_pass", "=", bad_pass_digest)],
                        columns=["feature_digest"])
    touched = set(tbl.column("feature_digest").to_pylist())
    return touched & shipped_digests

The intersection with shipped_digests matters: a faulty pass may have produced features that were superseded before they ever shipped, and re-verifying those is wasted work. What the standard asks is that the affected shipped set be complete, and this returns exactly it.

What the impact set looks like in practice, and why it is worth computing rather than assuming:

Impact Set against Whole-Release Re-Verification Nested proportional bars showing the full release, the features a faulty pass touched, and the shipped subset that actually needs re-verification. 412 000 features in the release 9 400 touched by the faulty pass 6 100 still shipped — the impact set 3 300 were superseded before release; re-verifying them proves nothing 1.5% of the release, and the claim that it is the complete affected set is checkable rather than asserted without digest-keyed provenance the only defensible answer is "re-verify everything", which is why nobody does

4. Answer the per-lane query #

python
def trace_lane(provenance_root, lane_digest: str) -> dict | None:
    tbl = pq.read_table(provenance_root,
                        filters=[("feature_digest", "=", lane_digest)])
    rows = tbl.to_pylist()
    return rows[0] if rows else None

Returning None for an unknown digest is the correct behaviour and the reason for keying by digest in the first place: a lane whose geometry has changed since the record was written simply does not resolve, instead of resolving to provenance that describes a different shape.

Verification & Acceptance Criteria #

python
def assert_traceability(provenance_root, release) -> None:
    missing = [f.digest for f in release.features
               if trace_lane(provenance_root, f.digest) is None]
    assert not missing, f"{len(missing)} shipped feature(s) have no provenance"

    for f in release.features[:1000]:
        rec = trace_lane(provenance_root, f.digest)
        assert store.exists(rec["survey_pass"]), "survey pass is not retrievable"
        assert store.exists(rec["toolchain"]), "toolchain image is not retrievable"

    edited = mutate_one_feature(release)
    assert trace_lane(provenance_root, edited.digest) is None, \
        "a changed feature inherited stale provenance"

Acceptance gate: zero shipped features without a provenance record; every referenced survey pass and toolchain retrievable from immutable storage; and a deliberately mutated feature that fails to resolve, which is the check proving the digest key is doing its job.

Why every reference in the record is a digest rather than a location:

Three Ways to Reference a Survey Pass Three rows pairing a reference style with what it points at and whether it survives as evidence. three ways to reference a survey pass from a provenance record path to a bucket object points at whatever is there today the object was reorganized not evidence ticket or build number points at a mutable record the tracker was migrated not evidence content digest points at exactly those bytes immutable by construction evidence only the third survives the two years between a build and the question somebody asks about it

Common Errors & Fixes #

Provenance resolves for a lane that has been re-surveyed. The record is keyed by feature identifier rather than digest. Re-key; the identifier belongs in the record as a field, not as the key.

A survey pass reference 404s two years later. The pass was stored at a mutable path and later reorganized. Address passes by digest in immutable storage and treat the path as a cache.

The provenance table is larger than the map. A record is being written per feature per release rather than per feature version. Deduplicate on digest before writing.

The impact set is empty for a pass you know was used. The pass digest changed between capture and build — usually re-compression. Digest the capture bundle once, at ingest, and carry that value forward.

Re-verification is scoped by tile rather than by feature. Tiles are coarse, so this over-scopes and looks conservative while actually hiding the question of completeness. Scope by the feature set the provenance names, then map to tiles for scheduling.

FAQ #

Why key provenance by content digest rather than by feature id? #

A feature identifier is stable across edits by design — that is what makes it useful for routing — so a record keyed by identifier survives a change to the geometry it describes and quietly becomes wrong. A content digest changes whenever the feature does, so a lane whose geometry was re-surveyed cannot carry the old provenance: the lookup simply misses, which is a detectable state rather than a plausible lie.

Does every release need the whole map re-verified? #

No, and a process that does is one nobody will run. What the standard requires is that a change invalidate the evidence for whatever it affects. If inputs are content-addressed, the affected set is computable: an edited survey pass invalidates exactly the features whose provenance names that pass, and everything else carries its existing verification forward. The discipline is in being able to prove the impact set is complete, not in re-running everything.

What has to be stored for a lane to be answerable years later? #

The survey pass digest and capture time, the operator or crew, the toolchain digest, the validation run identifier, and the feature digest that ties them to a specific geometry. Paths, ticket numbers and machine names are not enough: they name things that move. Anything referenced must itself be immutable, or the record points at whatever that reference holds today rather than what it held at build time.

Up one level: HD Map Quality Assurance & Certification — the assurance stage whose evidence this record is.