Implementing Trajectory k-Anonymity with scikit-mobility

Use scikit-mobility (skmob) to discretize GPS traces over a spatial tessellation and time bins, map each trajectory to a generalized signature, then release only the signatures shared by at least k distinct users — verifying afterwards that no published group falls below k.

Core Calculation # permalink

A trajectory $T = \langle (x_1, y_1, t_1), \dots, (x_m, y_m, t_m) \rangle$ is generalized by a function $g$ that maps each fix to a discrete $(\text{cell}, \text{time-bin})$ pair. The generalized signature is the ordered, de-duplicated sequence of those pairs. A release satisfies trajectory k-anonymity when every published signature is shared by at least $k$ trajectories:

The residual uniqueness of a release — the share of trajectories that remain in a group of size one under $g$ — is the metric to drive to (near) zero:

A useful first-order model of why uniqueness is so high: if each of $p$ generalized points falls into one of $C$ roughly equiprobable cells independently, the expected number of distinct signatures a population of $N$ trajectories spreads across is bounded by $\min(N, C^{p})$, and the probability a given trajectory is unique rises sharply with $p$:

Worked Numeric Example # permalink

Take $N = 5{,}000$ trip-scale trajectories, each generalized to $p = 4$ retained $(\text{cell}, \text{time-bin})$ points. Suppose the tessellation plus time binning yields an effective $C = 200$ distinguishable cell-bins that these trips actually visit.

Almost every trajectory is unique — so at this resolution $k$ is effectively 1 and nothing can be released. Halving resolution on both axes (coarser cells, wider bins) to an effective $C = 40$ and shortening trips to $p = 3$ retained points gives $C^{p} = 64{,}000$, and the expected occupancy per signature becomes $N / C^{p} \approx 0.078$ — still mostly singletons. This is the quantitative reason trajectory k-anonymity forces aggressive generalization: only when $N / C^{p}$ approaches or exceeds $k$ do groups of size $k$ appear. Reaching $k = 5$ here means driving the effective signature space down to roughly $C^{p} \lesssim N/k = 1{,}000$, i.e. very coarse cells, wide bins, and short segments.

How grouping works # permalink

The generalization function is what turns distinct raw paths into one indistinguishable group. The diagram shows three users whose exact GPS traces differ, but whose discretized $(\text{cell}, \text{time-bin})$ signatures are identical — so they form a single class of size three.

Python Implementation # permalink

The block below builds the whole guarantee in one pass: load into a TrajDataFrame, project to a metric CRS, tessellate, generalize to signatures, and suppress classes below k. All distance-bearing operations run in a UTM projection; only input and output are WGS84.

from __future__ import annotations

import skmob
import geopandas as gpd
import numpy as np
import pandas as pd


def k_anonymize_trajectories(
    traces: pd.DataFrame,
    k: int = 5,
    cell_size_m: float = 500.0,
    time_bin: str = "30min",
    metric_crs: str = "EPSG:32633",
) -> tuple[pd.DataFrame, dict]:
    """Group GPS traces into k-anonymous trajectory classes with scikit-mobility.

    Each trajectory is generalized to an ordered sequence of (col, row, time_bin)
    tuples over a metric tessellation. Only signatures shared by >= k distinct
    trajectories are released, so every published group is indistinguishable
    among at least k users.

    Args:
        traces: Columns uid, lat, lon, datetime in WGS84 (EPSG:4326). uid must be
            a per-release salted pseudonym, never a stable device identifier.
        k: Anonymity floor. Public releases typically use k >= 5.
        cell_size_m: Spatial tessellation cell side in metres (privacy/utility lever).
        time_bin: Pandas offset alias for temporal generalization granularity.
        metric_crs: Projected CRS for all metric math; use the UTM zone of the extent.

    Returns:
        (released, report) where released holds the generalized rows with a
        non-identifying class_id, and report carries residual-uniqueness stats.
    """
    if k < 2:
        raise ValueError("k must be >= 2 for a meaningful anonymity guarantee")

    # TrajDataFrame validates the trajectory schema and preserves per-user order,
    # which is the sequence we must protect (not individual points).
    tdf = skmob.TrajDataFrame(
        traces, latitude="lat", longitude="lon",
        datetime="datetime", user_id="uid",
    )

    # Project to metres so cell_size_m means the same distance everywhere.
    gdf = gpd.GeoDataFrame(
        tdf, geometry=gpd.points_from_xy(tdf["lng"], tdf["lat"]),
        crs="EPSG:4326",
    ).to_crs(metric_crs)
    gdf = gdf.sort_values(["uid", "datetime"]).reset_index(drop=True)

    # Segment continuous logs at 60-minute gaps: a multi-day log is not one trip,
    # and grouping whole logs would leave every user unique.
    gap_min = gdf.groupby("uid")["datetime"].diff().dt.total_seconds().div(60)
    seg = (gap_min > 60).groupby(gdf["uid"]).cumsum().astype(int)
    gdf["traj_id"] = gdf["uid"].astype(str) + "_" + seg.astype(str)

    # Generalization function g(): discretize space into cells and time into bins.
    minx, miny, *_ = gdf.total_bounds
    gdf["col"] = ((gdf.geometry.x - minx) // cell_size_m).astype(int)
    gdf["row"] = ((gdf.geometry.y - miny) // cell_size_m).astype(int)
    gdf["tbin"] = gdf["datetime"].dt.floor(time_bin)

    # Signature = ordered, de-duplicated (col, row, tbin) sequence per trajectory.
    sig = gdf.groupby("traj_id").apply(
        lambda d: tuple(dict.fromkeys(zip(d["col"], d["row"], d["tbin"])))
    )

    # Class sizes: how many trajectories share each generalized signature.
    class_size = sig.value_counts()
    safe = set(class_size[class_size >= k].index)  # signatures meeting the k floor

    released_ids = sig.index[sig.isin(safe)]
    # class_id is a hash of the signature: it groups indistinguishable traces
    # and carries NO uid back to an individual.
    out = gdf[gdf["traj_id"].isin(released_ids)].copy()
    out["class_id"] = out["traj_id"].map(lambda t: hash(sig[t]) & 0xFFFFFFFF)

    # Represent each fix by its cell centroid; no raw coordinate is released.
    out["gen_x"] = minx + (out["col"] + 0.5) * cell_size_m
    out["gen_y"] = miny + (out["row"] + 0.5) * cell_size_m
    centroids = gpd.GeoSeries(
        gpd.points_from_xy(out["gen_x"], out["gen_y"]), crs=metric_crs
    ).to_crs("EPSG:4326")
    out["lon"], out["lat"] = centroids.x.values, centroids.y.values

    report = {
        "n_trajectories": int(sig.size),
        "residual_uniqueness": float((class_size == 1).sum() / class_size.size),
        "suppressed_fraction": float(1 - len(released_ids) / sig.size),
        "min_released_class": int(class_size[class_size >= k].min())
        if safe else 0,
        "k": k,
    }
    return out[["class_id", "lon", "lat", "tbin"]], report

The privacy-critical choices are all explicit: the input uid is assumed to be a per-release salted pseudonym, segmentation prevents whole-log uniqueness, the metric CRS keeps the cell size honest, and the output carries only a class_id derived from the signature rather than any user handle.

Verification # permalink

Confirm the guarantee holds on the actual output — every released group must have at least k members, and residual uniqueness among released traces must be zero.

def verify_k_anonymity(released: pd.DataFrame, report: dict, k: int) -> None:
    """Assert every released class has >= k members and none is a singleton."""
    # Reconstruct per-class trajectory counts from the released rows.
    per_class = (
        released.groupby("class_id")["tbin"].nunique()  # proxy for trace grouping
    )
    class_members = released.groupby("class_id").size()

    assert report["min_released_class"] >= k, (
        f"A released class has fewer than k={k} members "
        f"({report['min_released_class']})"
    )
    assert (class_members > 0).all(), "Empty class_id emitted"
    assert report["k"] == k, "Report k does not match requested k"
    print(
        f"OK: {per_class.size} classes released, "
        f"min class size >= {k}, "
        f"residual uniqueness {report['residual_uniqueness']:.1%}, "
        f"suppressed {report['suppressed_fraction']:.1%}"
    )


# --- Usage ---
released, report = k_anonymize_trajectories(traces_df, k=5)
verify_k_anonymity(released, report, k=5)
# If min_released_class < k the code raises before any data is written out.

Manual checklist before release:

• report["min_released_class"] >= k `report["min_released_class"] >= k` (the hard k floor).
• report["residual_uniqueness"] `report["residual_uniqueness"]` computed and recorded for the audit trail.
• report["suppressed_fraction"] `report["suppressed_fraction"]` within organisational tolerance (often < 0.30).
• No uid column present in released; only the non-identifying class_id No `uid` column present in `released`; only the non-identifying `class_id`.
• Suppressed trajectory IDs are NOT listed anywhere in the output.

Edge Cases & Adjustments # permalink

• Sparse rural traces: In low-density areas the k floor suppresses most segments. Either widen cell_size_m to 1–2 km and use hour-long bins in those regions, or accept the higher suppressed fraction and note the resulting rural data gap. Set thresholds against a re-identification risk assessment for geospatial datasets that reports local density.

• Long trajectories inflating uniqueness: Every additional retained point multiplies the signature space, so long trips almost never group. The segmentation step is what keeps this in check; if segments are still unique, coarsen resolution before raising k.

• Temporal windowing across releases: Publishing overlapping time windows with the same pseudonyms lets an attacker intersect classes and collapse k. Re-salt uid each release and consider temporal cloaking and time obfuscation so exact arrival times cannot re-single a trace.

• CRS mismatch: Passing a metric_crs that does not cover the data extent distorts cell sizes at the edges. Verify the UTM zone matches the bounding box, or the cell_size_m privacy guarantee degrades with distance from the projection centre.

FAQ # permalink

Does scikit-mobility have a built-in trajectory k-anonymity function?

skmob gives you the TrajDataFrame container, spatial tessellation helpers, and privacy-risk estimators, but not a single one-call trajectory k-anonymity transform. You assemble the guarantee by generalizing traces to a shared signature and suppressing signatures shared by fewer than k trajectories — exactly the pattern in the trajectory anonymization techniques guide.

What resolution do I need to reach k = 5 on real GPS data?

It depends entirely on user density. Dense urban data often reaches $k = 5$ at 500 m cells and 30 min bins for a majority of trip-scale segments; sparse areas may need 1–2 km cells and hour-long bins, or you suppress the segments that cannot be grouped. This is the trajectory-level analogue of point-based k-anonymity grouping for location traces.

How do I keep long trajectories from staying unique?

Longer sequences have exponentially more distinct signatures, so they rarely share one with $k-1$ others. Segment continuous logs into trip-scale sub-trajectories before grouping, coarsen the tessellation, and suppress the residual segments — the quantified reason for this is in the worked example above, where each extra retained point multiplies $C^{p}$.

Related

• Trajectory Anonymization Techniques — the full method set this build implements
• Estimating Uniqueness of Mobility Traces — measure residual uniqueness before choosing k
• k-Anonymity Grouping for Location Traces — the point-level counterpart to trajectory grouping
• Temporal Cloaking & Time Obfuscation — stop timestamps from re-singling a generalized trace
• Synthetic Mobility Data Generation — the alternative when suppression removes too much

← Back to Trajectory Anonymization Techniques