Partitioning Datasets with H3 for Parallel Validation

Parallel validation is easy for per-feature rules and subtle for everything else. Split a coverage into chunks, run an overlap check on each, and you will miss every overlap that crosses a chunk boundary — silently, with no error and a plausible-looking report. H3 gives a clean way to do it correctly: a hierarchical hexagonal index where every cell has exactly six neighbours at a uniform distance, which makes the halo pattern — including neighbouring cells read-only so boundary-crossing relationships stay visible — straightforward to implement and to reason about. This guide covers resolution choice, assignment, halos, execution and deduplication, implementing the partitioning strategy from Batch Processing Large Spatial Datasets.

Prerequisites

• h3 4.x (pip install h3), geopandas 0.14+, shapely 2.0+.
• Data in WGS 84 for indexing. H3 works in geographic coordinates; keep a projected copy for measurement, and index on the geographic one.
• A worker memory budget. The resolution choice is derived from it, so it needs a number rather than an intention.
• A findings contract with a deterministic key — the deduplication in Step 5 depends on being able to identify the same finding produced by two partitions.

Step-by-Step Procedure

Step 1 — Choose the resolution from the densest area

# h3_partition/step1_resolution.py
import geopandas as gpd
import h3
import pandas as pd

APPROX_EDGE_KM = {5: 8.5, 6: 3.2, 7: 1.2, 8: 0.46, 9: 0.17, 10: 0.065}


def resolution_profile(gdf_wgs84: gpd.GeoDataFrame,
                       candidates=(6, 7, 8, 9)) -> pd.DataFrame:
    """Feature count per cell at each candidate resolution."""
    pts = gdf_wgs84.geometry.representative_point()
    rows = []
    for res in candidates:
        cells = [h3.latlng_to_cell(p.y, p.x, res) for p in pts]
        counts = pd.Series(cells).value_counts()
        rows.append({
            "resolution": res,
            "approx_edge_km": APPROX_EDGE_KM.get(res),
            "cells": int(counts.size),
            "median_features": int(counts.median()),
            "p95_features": int(counts.quantile(0.95)),
            "max_features": int(counts.max()),
        })
    return pd.DataFrame(rows)

Verification: pick the resolution whose p95_features sits in the 20,000–100,000 range. The max_features column matters too — one enormous cell over a city centre becomes the straggler that determines total wall-clock time, and dropping one resolution level to split it is usually worth the extra scheduling overhead.

Step 2 — Assign cells, and record what each feature touches

# h3_partition/step2_assign.py
import geopandas as gpd
import h3
from shapely.geometry import mapping


def assign_cells(gdf: gpd.GeoDataFrame, res: int) -> gpd.GeoDataFrame:
    """Home cell from the representative point; touched cells from the full geometry."""
    out = gdf.copy()
    pts = out.geometry.representative_point()
    out["h3_home"] = [h3.latlng_to_cell(p.y, p.x, res) for p in pts]
    out["h3_touched"] = [sorted(_cells_for(geom, res)) for geom in out.geometry]
    out["straddles"] = [len(c) > 1 for c in out["h3_touched"]]
    return out


def _cells_for(geom, res: int) -> set[str]:
    """Every cell the geometry intersects — polyfill plus the boundary vertices."""
    if geom.geom_type in ("Point", "MultiPoint"):
        return {h3.latlng_to_cell(p.y, p.x, res) for p in
                (geom.geoms if geom.geom_type == "MultiPoint" else [geom])}
    cells = set(h3.geo_to_cells(mapping(geom), res))
    # polyfill misses cells that the boundary only clips; add the vertex cells.
    for x, y in geom.exterior.coords if geom.geom_type == "Polygon" else []:
        cells.add(h3.latlng_to_cell(y, x, res))
    return cells or {h3.latlng_to_cell(geom.centroid.y, geom.centroid.x, res)}

Verification: the straddles share tells you how much duplication the halo will cause. For parcels at a well-chosen resolution it is typically a few percent; if it is 40%, the resolution is too fine for the feature size and every partition will be mostly halo.

Step 3 — Build halo partitions

# h3_partition/step3_halo.py
import h3


def partition_spec(cell: str, ring: int = 1) -> dict:
    """A partition is one core cell plus a read-only ring of neighbours."""
    neighbours = set(h3.grid_disk(cell, ring)) - {cell}
    return {"partition_id": cell, "core_cells": [cell],
            "halo_cells": sorted(neighbours), "ring": ring}


def build_partition(gdf, spec: dict):
    """Core features are validated and reported; halo features are context only."""
    core_mask = gdf["h3_home"].isin(spec["core_cells"])
    halo_mask = (~core_mask) & gdf["h3_touched"].map(
        lambda cells: any(c in spec["halo_cells"] or c in spec["core_cells"] for c in cells))
    core = gdf[core_mask].assign(_role="core")
    halo = gdf[halo_mask].assign(_role="halo")
    import pandas as pd
    return pd.concat([core, halo])

Verification: a ring of 1 is sufficient when features are smaller than a cell — the usual case. If any feature spans more than one cell width, the ring must be large enough to contain the largest feature, or a relationship between two large features can still be split. Check the maximum feature extent against the cell edge length before settling on ring=1.

Step 4 — Run the rules per partition

# h3_partition/step4_run.py
from concurrent.futures import ProcessPoolExecutor, as_completed


def validate_partition(args) -> list[dict]:
    gdf, spec, rules = args
    part = build_partition(gdf, spec)
    findings = []
    for rule in rules:
        for f in rule(part):
            # Only report a finding if at least one participant is core to this partition.
            participants = f.get("feature_ids", [f["feature_id"]])
            if any(part.loc[part.index.isin(participants), "_role"].eq("core").any()
                   for _ in [0]):
                findings.append({**f, "partition_id": spec["partition_id"]})
    return findings


def run_all(gdf, specs, rules, workers: int = 8) -> list[dict]:
    out = []
    with ProcessPoolExecutor(max_workers=workers) as pool:
        futures = [pool.submit(validate_partition, (gdf, s, rules)) for s in specs]
        for fut in as_completed(futures):
            out.extend(fut.result())
    return out

Verification: the core/halo distinction in the reporting condition is what keeps halo-only relationships from being reported by a partition that has no stake in them. Without it, a pair of features both in the halo of partition A — and both core to partition B — gets reported by A as well, multiplying duplication unnecessarily.

Step 5 — Deduplicate on a deterministic key

# h3_partition/step5_dedupe.py
import hashlib


def finding_key(f: dict) -> str:
    """Identical relationships found from different partitions must produce one key."""
    ids = sorted(str(i) for i in f.get("feature_ids", [f["feature_id"]]))
    payload = "|".join([f["rule"], *ids])
    return hashlib.sha256(payload.encode()).hexdigest()[:16]


def deduplicate(findings: list[dict]) -> list[dict]:
    seen: dict[str, dict] = {}
    for f in findings:
        key = finding_key(f)
        if key not in seen:
            seen[key] = {**f, "key": key, "reported_by": [f["partition_id"]]}
        else:
            seen[key]["reported_by"].append(f["partition_id"])
    return list(seen.values())


def duplication_report(deduped: list[dict]) -> dict:
    multi = [f for f in deduped if len(f["reported_by"]) > 1]
    return {
        "unique_findings": len(deduped),
        "reported_more_than_once": len(multi),
        "duplication_rate": round(len(multi) / max(len(deduped), 1), 4),
    }

Verification: the duplication rate is a health metric for the partitioning. Near zero means almost nothing crosses boundaries — the resolution may be coarser than necessary. Above roughly 20% means many relationships straddle cells, and a coarser resolution would do less redundant work.

Interpreting Results

The control run is worth doing once: validate the whole layer unpartitioned on a smaller extent, then validate the same extent partitioned, and compare the deduplicated findings. They must match exactly. That test catches halo and reporting-condition bugs, which are otherwise invisible — a partitioned run that misses findings looks identical to a clean dataset.

Gotchas & Edge Cases

Polyfill misses cells clipped only by an edge. geo_to_cells returns cells whose centres fall inside the polygon, so a long thin feature can pass through a cell without its centre being contained. Adding the boundary vertex cells, as in Step 2, covers the common cases; for very elongated features, buffer the geometry slightly before polyfilling.

H3 indexes in geographic coordinates and measures in projected ones. Assign cells from WGS 84 and compute areas, distances and tolerances in the projected copy. Mixing them produces cells that are correct and measurements that are not.

Cell area varies with latitude. H3 cells are not equal-area; a resolution 8 cell near the equator differs noticeably from one at 60 degrees. For feature-count-based partitioning this does not matter, because the count is what you tuned. For anything reporting per-cell densities, it does.

A feature exactly on a cell boundary is assigned by its representative point. That is deterministic and arbitrary, which is fine — the halo ensures its relationships are still visible from the neighbouring partition.

Deduplication keys must not include the partition. An obvious slip, and it silently disables deduplication because every finding then has a unique key.

Findings involving three or more features need all identifiers in the key. A gap bounded by four parcels reported from two partitions must collapse to one finding; sorting all four identifiers into the key achieves that, keying on one of them does not.

When to Escalate

• A control run that does not match the partitioned run is a correctness bug and blocks the partitioning entirely. Do not tune resolutions until it matches.
• A hotspot cell that cannot be split further — resolution 10 or finer with tens of thousands of features — usually means the data has genuine density that needs a different strategy, such as splitting by feature class rather than by geography.
• Cross-partition rules that cannot be expressed with a halo — coverage completeness over the whole layer, for instance — are not partitionable. Run them as a single-pass job, as noted in the scaling model in Validation Pipeline Architecture.
• Duplication rates that stay high at every resolution suggest the features are unsuited to spatial partitioning at all; consider partitioning by an attribute key instead.

Frequently Asked Questions

Related

• Batch Processing Large Spatial Datasets — the wider batch design this partitioning serves
• Scaling GeoPandas Validation with Dask — distributing the partitions once they are defined
• Finding Gaps and Overlaps in Polygon Coverages with PostGIS — the cross-feature rules that need the halo

Back to Batch Processing Large Spatial Datasets