Duplicate Detection & Feature Deduplication Jump to heading#

Every other gate in this section tests a property that is true or false about the data in front of it. This one tests a claim about the world: that two records describe the same thing. Nothing in the geometry or the attributes proves it — two address points 40 cm apart with slightly different street spellings might be one building recorded twice, or a house and its granny flat. That is why deduplication is the last gate of Spatial Data Quality Validation & Geometry Integrity and the one where the discipline is hardest to hold: the matching is inherently a judgement, so the decision procedure has to carry all the determinism the matching cannot.

The position taken here is a narrow one. Match rules may be fuzzy — a distance threshold, a normalized string comparison, an attribute agreement count — but a rule is a declared, version-controlled combination of those tests, and the survivor of a matched group is chosen by a stated precedence order rather than by whichever row the reader happened to yield first. Two runs over the same input must produce the same surviving features, the same merged attributes, and the same audit record, on any machine, in any partition order. Where the rules cannot decide, the group is quarantined for a human rather than resolved by a tiebreak nobody wrote down.

This page owns duplicates within a delivery and across deliveries of the same layer. It does not own conflation between fundamentally different datasets — matching a building footprint layer to a business registry is an entity-resolution problem with its own accuracy requirements — and it does not own the identifiers themselves, which come from the schema architecture work upstream.

Why the Match Rule Comes Before the Algorithm Jump to heading#

Teams reliably start with the clustering algorithm and discover the rule afterwards, which is backwards: the algorithm is an implementation detail of a rule that ought to be legible to a data steward who has never read Python.

The middle column is the one that makes the rule honest. A two-outcome rule — match or no match — forces every ambiguous pair into one of them, and the choice is made by whoever picked the threshold. A three-outcome rule admits that some pairs cannot be decided from the data, sizes that population explicitly, and puts it in front of a person. When the review queue is large, the rule is wrong; when it is empty, the thresholds are probably too loose. Both are measurements you only get if the middle outcome exists.

Declarative Configuration Manifest Jump to heading#

# dedup_rules.yaml — geopandas >=0.14, pyyaml >=6.0
manifest_version: "1.2.0"        # MANDATORY
crs: "EPSG:25832"                # MANDATORY: projected; radii are in its units
rules:
  - name: address_points_within_postcode
    layer: address_points        # MANDATORY
    blocking_key: ["postcode"]   # MANDATORY: no cross-block comparison ever happens
    spatial:
      predicate: dwithin         # MANDATORY: dwithin | intersects | equals_exact
      radius: 2.0                # MANDATORY for dwithin, in CRS units
    agreement:                   # MANDATORY: the fields that vote
      - field: street_name
        normalize: casefold_strip_punctuation
      - field: house_number
        normalize: strip_leading_zeros
      - field: unit_designator
        normalize: casefold
    thresholds:
      auto_match: 3              # MANDATORY: agreeing fields for an automatic match
      review: 2                  # MANDATORY: agreeing fields for the review queue
    survivor:                    # MANDATORY: precedence, evaluated in order
      - prefer: source_rank      # 1. lowest source rank wins (authoritative source)
        order: asc
      - prefer: last_verified    # 2. most recently verified
        order: desc
      - prefer: completeness     # 3. most non-null declared fields
        order: desc
      - prefer: feature_id       # 4. deterministic tiebreak — never omit this
        order: asc
    merge:
      attributes: fill_nulls_from_losers   # OPTIONAL: none | fill_nulls_from_losers
      geometry: keep_survivor              # OPTIONAL: keep_survivor | centroid_of_group
    on_unresolved: quarantine_group        # MANDATORY: review candidates left undecided

The survivor list ends with feature_id for a reason that is easy to under-rate: without a total order at the bottom, two records that tie on every declared criterion are resolved by row order, which changes with partitioning, with parallelism, and with the reader’s buffer size. That single omission is the most common cause of a deduplication stage that produces different output on the same input, and it is invisible until someone diffs two runs.

Preprocessing Requirements Jump to heading#

Blocking is a correctness decision, not just an optimization. Comparing every pair in a national address layer is quadratic and impossible; blocking by postcode makes it linear in practice. But blocking also defines which duplicates are findable: two records for one building that disagree on postcode will never be compared, and that is a deliberate, documented limitation rather than an oversight. State it in the quality report so consumers know what the deduplication does not cover.

Normalization is declared and applied identically to both sides. casefold_strip_punctuation must be one function with one implementation and a test, used by the matcher, by the review tool a steward uses, and by the report. Two slightly different normalizations produce a review queue full of pairs that look identical to a human, which destroys confidence in the whole gate.

Geometry has already been validated and reprojected. Duplicate detection runs last because a dwithin radius in metres requires a projected CRS, and because comparing a repaired geometry against its unrepaired twin produces a match on the pair least worth matching.

Execution Engine & Precision Guards Jump to heading#

# quality/dedup.py — geopandas >=0.14, shapely >=2.0 — Python 3.10+
import logging
from dataclasses import dataclass
from itertools import combinations

import geopandas as gpd
from shapely import STRtree

logger = logging.getLogger("quality.dedup")

NORMALIZERS = {
    "casefold": lambda v: (v or "").casefold().strip(),
    "casefold_strip_punctuation":
        lambda v: "".join(c for c in (v or "").casefold() if c.isalnum() or c.isspace()).strip(),
    "strip_leading_zeros": lambda v: (v or "").lstrip("0") or "0",
}


@dataclass(frozen=True)
class Pair:
    left_id: str
    right_id: str
    distance: float
    agreeing: int
    outcome: str        # match | review | no_match


def agreement_count(left: dict, right: dict, specs: list[dict]) -> int:
    agree = 0
    for spec in specs:
        fn = NORMALIZERS[spec["normalize"]]        # KeyError is intentional: unknown = bug
        if fn(left.get(spec["field"])) == fn(right.get(spec["field"])):
            agree += 1
    return agree


def find_pairs(block: gpd.GeoDataFrame, rule: dict) -> list[Pair]:
    """All candidate pairs within one blocking group, evaluated deterministically."""
    if block.crs is None or block.crs.is_geographic:
        raise ValueError(f"{rule['name']}: radius in CRS units requires a projected CRS")

    block = block.sort_values("feature_id").reset_index(drop=True)   # order-independence
    radius = rule["spatial"]["radius"]
    tree = STRtree(block.geometry.values)
    records = block.to_dict("records")
    pairs: list[Pair] = []

    left_idx, right_idx = tree.query(block.geometry.values, predicate="dwithin",
                                     distance=radius)
    for i, j in zip(left_idx.tolist(), right_idx.tolist()):
        if i >= j:
            continue                    # each unordered pair exactly once, sorted order
        left, right = records[i], records[j]
        agreeing = agreement_count(left, right, rule["agreement"])
        if agreeing >= rule["thresholds"]["auto_match"]:
            outcome = "match"
        elif agreeing >= rule["thresholds"]["review"]:
            outcome = "review"
        else:
            outcome = "no_match"
        if outcome != "no_match":
            distance = block.geometry.iloc[i].distance(block.geometry.iloc[j])
            pairs.append(Pair(left["feature_id"], right["feature_id"],
                              distance, agreeing, outcome))

    logger.info("rule=%s block=%s pairs=%d", rule["name"], block.iloc[0].get("postcode"),
                len(pairs))
    return pairs


def choose_survivor(group: list[dict], precedence: list[dict]) -> dict:
    """Apply the precedence list in order; the final key must be a total order."""
    def sort_key(record: dict):
        key = []
        for step in precedence:
            value = record.get(step["prefer"])
            key.append(value if step["order"] == "asc" else _negate(value))
        return tuple(key)

    return sorted(group, key=sort_key)[0]

The i >= j skip, the sort by feature_id before evaluation, and the total-order tiebreak in choose_survivor are the three lines that make this stage reproducible. None of them affects which pairs are found — they affect only whether two runs agree on what to do about them, which is the difference between a gate and a coin toss.

Transitivity is the remaining subtlety. If A matches B and B matches C but A does not match C, the group is a chain rather than a clique. Resolving chains by taking connected components merges records the rule never said were the same; resolving them by requiring a clique leaves genuine triples unmerged. The manifest must state which, and the honest default for authoritative data is to require the clique and send chains to review — a three-record chain is usually a sign that the radius is slightly too generous.

Failure Modes & Fallback Routing Jump to heading#

DUP_BLOCK_TOO_LARGE deserves the hard failure it gets. The usual cause is nulls collapsing into a single block, and the usual symptom without the check is a job that runs for eleven hours and then produces a review queue with two million entries. Asserting a maximum block size turns an operational disaster into a manifest fix.

Compliance Reporting Output Jump to heading#

# quality/dedup_report.py — pyarrow >=14 — Python 3.10+
import pyarrow as pa

DEDUP_REPORT_SCHEMA = pa.schema([
    ("dataset_id",       pa.string()),
    ("run_id",           pa.string()),
    ("manifest_version", pa.string()),
    ("rule_name",        pa.string()),
    ("match_radius",     pa.float64()),   # published so consumers can judge coverage
    ("blocking_key",     pa.string()),    # states what the rule cannot find
    ("records_in",       pa.int64()),
    ("pairs_compared",   pa.int64()),
    ("auto_matched",     pa.int64()),
    ("review_pending",   pa.int64()),
    ("records_out",      pa.int64()),     # records_in minus absorbed records
    ("result",           pa.string()),
])

MERGE_RECORD_SCHEMA = pa.schema([
    ("run_id",           pa.string()),
    ("survivor_id",      pa.string()),
    ("absorbed_id",      pa.string()),    # one row per absorbed record
    ("agreeing_fields",  pa.int64()),
    ("distance",         pa.float64()),
    ("precedence_step",  pa.string()),    # which rule decided the survivor
    ("attributes_filled", pa.string()),   # comma-separated fields inherited from the loser
])

The second table is what makes a merge reversible. Recording precedence_step — that the survivor won on last_verified rather than on source_rank — is the difference between “we merged 4,102 records” and an audit trail that can explain any one of them. Recording attributes_filled matters just as much: a survivor that inherited a phone number from a record that no longer exists is carrying an assertion whose provenance would otherwise vanish. Both tables join the lineage manifest on run_id and contribute the completeness-commission element of the ISO 19157 quality report.

CI Integration Jump to heading#

# tests/test_dedup.py — pytest >=7, geopandas >=0.14
import geopandas as gpd
import pytest

from quality.dedup import find_pairs, choose_survivor
from quality.manifest import load_dedup_rules

RULE = load_dedup_rules("dedup_rules.yaml")["address_points_within_postcode"]


@pytest.fixture(scope="module")
def block() -> gpd.GeoDataFrame:
    return gpd.read_file("tests/fixtures/address_points_one_postcode.gpkg")


def test_identical_addresses_auto_match(block):
    outcomes = {(p.left_id, p.right_id): p.outcome for p in find_pairs(block, RULE)}
    assert outcomes[("AP-0001", "AP-0002")] == "match"


def test_house_and_annexe_are_review_not_match(block):
    # 0.8 m apart, same street, different unit designator: two fields agree.
    outcomes = {(p.left_id, p.right_id): p.outcome for p in find_pairs(block, RULE)}
    assert outcomes[("AP-0007", "AP-0008")] == "review"


def test_pair_order_is_stable_under_shuffling(block):
    a = find_pairs(block, RULE)
    b = find_pairs(block.sample(frac=1.0, random_state=7), RULE)
    assert [(p.left_id, p.right_id, p.outcome) for p in a] == \
           [(p.left_id, p.right_id, p.outcome) for p in b]


def test_survivor_precedence_has_a_total_order():
    # Negative control: a precedence list without a unique final key must be refused.
    with pytest.raises(ValueError):
        choose_survivor([{"feature_id": "a"}, {"feature_id": "b"}],
                        precedence=[{"prefer": "source_rank", "order": "asc"}])

The shuffle test is the one that catches regressions nothing else will. Any change that reintroduces reliance on input order — a groupby without a sort, a parallel map that returns out of sequence — fails it immediately, and the failure message points at the pair whose outcome moved.

Deeper Implementation Walkthroughs Jump to heading#

Deduplicating address points with spatial clustering implements the blocking-plus-radius approach at municipal scale and shows where a clustering algorithm helps and where it quietly changes the rule. Matching features across vintages with stable identifiers handles the harder cross-delivery case, where the goal is not to remove a record but to recognize that this year’s parcel is last year’s parcel with a new boundary.

Frequently Asked Questions Jump to heading#

Why not use DBSCAN or an off-the-shelf clustering library? Clustering is a fine implementation of the pair-finding step, and for dense point layers it is faster than an index query per record. What it cannot do is express the rule: DBSCAN groups by density, so a run of terraced houses 1.5 m apart becomes one cluster of forty records, none of which are duplicates. If you use clustering, use it to generate candidate pairs and then apply the agreement test to each pair — never treat a cluster as a merge group.

Should the survivor’s geometry be the centroid of the group? Rarely. A centroid is a position no source ever asserted, which makes it unattributable and, for address points, frequently wrong — the centroid of a doorway record and a rooftop record sits in the middle of a wall. keep_survivor preserves a position with known provenance. The exception is when the group represents repeated observations of one thing whose true position is unknown, where an averaged position is a defensible estimate and must be recorded as one.

What happens to the identifiers of absorbed records? They must remain resolvable. Downstream systems, printed reports and citizens’ correspondence all carry them, and a record that vanishes without a forwarding address turns into a support ticket. The merge record is the forwarding address: absorbed identifier, survivor identifier, run, and reason. Publishing that mapping alongside the dataset is cheap and prevents the most common post-deduplication complaint.

How do we set the match radius? From the positional accuracy of the sources, not from what produces a satisfying number of matches. If two sources are each accurate to ±0.5 m, a 2 m radius is generous but defensible; a 10 m radius is asserting that the sources are far worse than they claim. Where accuracy figures exist, the CRS normalization stage already records them per feature, and deriving the radius from that record is more defensible than any tuned constant.

Related Jump to heading#

• Spatial Data Quality Validation & Geometry Integrity — the parent section and why deduplication runs last
• Deduplicating Address Points with Spatial Clustering — blocking, radius and review queue at municipal scale
• Matching Features Across Vintages with Stable IDs — identity across deliveries rather than within one
• Attribute Domain & Code List Validation — the previous gate, which surfaces the non-unique identifiers this one resolves
• Lineage Manifest Generation — where merge records are retained as permanent, addressable evidence
• Reconciling Parcel Field Names Across Counties — the upstream vocabulary alignment that makes attribute agreement meaningful