Trajectory Anonymization Techniques

Trajectory anonymization protects an entire ordered movement sequence — the path a person traces through space and time — rather than isolated coordinate points, because it is the shape and rhythm of a whole journey, not any single location, that makes mobility data uniquely identifying.

A single home-to-work commute observed at even coarse resolution is enough to single out one individual among millions; four approximate spatio-temporal points are sufficient to uniquely identify roughly 95% of people in a mobility dataset. Anonymizing points in isolation does nothing to defeat an adversary who reconnects them into a path, so trajectory-level methods operate on the sequence as the unit of protection.

When to Use Each Technique # permalink

The four core families — trajectory k-anonymity, segment suppression, generalization, and synthetic replacement — trade utility against protection differently. The decision hinges on how much fidelity the downstream use-case needs, how strong an adversary you model, and whether you must publish individual raw-looking paths or can release an aggregate.

The four families are not mutually exclusive. A production pipeline usually generalizes the bulk of each trajectory, suppresses the small number of segments that remain unique, and only reaches for synthetic replacement when even aggressive generalization cannot hit the target k without erasing the analytical signal.

Algorithmic Specification # permalink

Trajectory k-Anonymity # permalink

Let a trajectory be an ordered sequence of spatio-temporal points $T = \langle (x_1, y_1, t_1), \dots, (x_m, y_m, t_m) \rangle$. A published dataset $D^{*}$ satisfies trajectory k-anonymity if every released trajectory is identical, under the chosen generalization function $g$, to at least $k-1$ others:

The set of traces sharing a generalized representation is an equivalence class. The effective anonymity of the release is the smallest class actually published:

(k, δ)-Anonymity for Trajectories # permalink

Exact equality of continuous GPS paths almost never occurs, so the practical relaxation treats trajectories as cylindrical volumes of radius $\delta$ in space. A group of trajectories is (k, δ)-anonymous if it contains at least $k$ traces and, at every timestamp, all members lie within a disc of radius $\delta$ — that is, they are co-localized within the uncertainty $\delta$ across their whole common lifespan:

The released representative for the group is the centre trace of the cylinder; each member is indistinguishable from the others to within $\delta$. Larger $\delta$ makes groups easier to form (higher utility coverage) but coarsens location precision.

Spatio-Temporal Cloaking Radius # permalink

Cloaking replaces each true point with a region large enough to contain $k$ users. For a target $k$ over a local user density $\rho$ (users per square metre) sampled in the relevant time window, the minimum cloaking radius is:

This is why the same $k$ demands a small radius in a dense city centre and a very large one in a rural area — the re-identification risk assessment for geospatial datasets that precedes anonymization should therefore report density, not just record counts.

Parameter Reference # permalink

Prerequisites & Data Requirements # permalink

Before running any trajectory anonymization pipeline, confirm the following:

• Trace schema: Each record must carry a stable pseudonymous uid, lat, lon, and a timestamp. Direct identifiers (device IDs, account numbers) must already be stripped; the uid should be a per-release salted pseudonym so it cannot be joined across publications.
• Coordinate reference system: Raw traces arrive in WGS84 (EPSG:4326). All distance, radius, and cell operations must run in a projected metric CRS — the appropriate UTM zone for the dataset extent — then results are reprojected back to WGS84 for release. Computing $\delta$ or $r_{\text{cloak}}$ in degrees silently distorts protection with latitude.
• Minimum number of traces: Trajectory k-anonymity needs enough overlapping users to form classes of size $k$. As a rule of thumb, you need far more than $k$ users; sparse datasets with fewer than roughly $50 \times k$ distinct trajectories in the study area will suppress the majority of paths.
• Temporal coverage: Traces should share a common observation window. Grouping requires time alignment, so define the resampling interval before processing.
• Python dependencies: scikit-mobility (skmob) for trajectory structures and tessellation, geopandas ≥ 0.14 and shapely ≥ 2.0 for geometry, numpy, and pyproj for CRS transforms.

Step-by-Step Implementation # permalink

The workflow below segments raw traces, groups them into k-anonymity equivalence classes over a spatial tessellation, and generalizes each class to a shared representation. It uses skmob for the trajectory abstractions and geopandas for the metric operations.

Step 1 — Load Traces and Standardize CRS # permalink

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

# Raw GPS logs: columns uid, lat, lon, datetime — WGS84 (EPSG:4326).
raw = pd.read_parquet("raw_traces.parquet")

# TrajDataFrame is skmob's typed trajectory container; it validates the schema
# and preserves per-user ordering, which is the unit we must protect.
tdf: TrajDataFrame = skmob.TrajDataFrame(
    raw, latitude="lat", longitude="lon", datetime="datetime", user_id="uid"
)

# Reproject to a metric CRS for all radius/distance math. Choose the UTM zone
# that covers the dataset extent; here EPSG:32633 (UTM 33N) as an example.
METRIC_CRS = "EPSG:32633"
gdf = gpd.GeoDataFrame(
    tdf,
    geometry=gpd.points_from_xy(tdf["lng"], tdf["lat"]),
    crs="EPSG:4326",
).to_crs(METRIC_CRS)

Reprojection is a privacy step: a co-location radius $\delta$ expressed in metres only means the same thing everywhere once coordinates are metric.

Step 2 — Segment Continuous Traces # permalink

# Split each user's continuous log into comparable sub-trajectories at large
# temporal gaps. A multi-day log is not one trajectory; grouping whole logs
# would leave every user in a class of size 1.
GAP_MINUTES = 60

gdf = gdf.sort_values(["uid", "datetime"]).copy()
gdf["gap"] = (
    gdf.groupby("uid")["datetime"].diff().dt.total_seconds().div(60)
)
# A new segment starts whenever the gap since the previous fix exceeds GAP_MINUTES.
gdf["segment"] = (
    (gdf["gap"] > GAP_MINUTES).groupby(gdf["uid"]).cumsum().astype(int)
)
gdf["traj_id"] = gdf["uid"].astype(str) + "_" + gdf["segment"].astype(str)

Segmentation controls trajectory length. Long traces are almost always unique, so cutting logs into trip-scale segments is what makes any grouping feasible at all.

Step 3 — Tessellate and Discretize # permalink

# Discretize space into cells and time into bins. Two fixes are "equivalent"
# when they share the same (cell, time-bin); this is the generalization
# function g() from the k-anonymity definition.
CELL_SIZE = 500     # metres — see r_cloak / density analysis for the right value
TIME_BIN = "30min"  # temporal granularity

minx, miny, _, _ = gdf.total_bounds
gdf["col"] = ((gdf.geometry.x - minx) // CELL_SIZE).astype(int)
gdf["row"] = ((gdf.geometry.y - miny) // CELL_SIZE).astype(int)
gdf["tbin"] = gdf["datetime"].dt.floor(TIME_BIN)

# The generalized signature of a trajectory is its ordered sequence of
# (cell, time-bin) tuples — the key we group indistinguishable traces on.
sig = (
    gdf.groupby("traj_id")
    .apply(lambda d: tuple(zip(d["col"], d["row"], d["tbin"])))
    .rename("signature")
)

Coarser cells and wider time bins pull more traces into each signature, raising $k$ at the cost of spatial and temporal resolution — the core privacy-utility lever.

Step 4 — Form k-Anonymity Classes and Suppress # permalink

K = 5  # anonymity floor for a public release

# Count how many distinct trajectories share each generalized signature.
class_size = sig.value_counts()
safe_signatures = set(class_size[class_size >= K].index)

# Trajectories whose signature is rarer than k cannot be released as-is.
sig_df = sig.reset_index()
sig_df["released"] = sig_df["signature"].isin(safe_signatures)

released_ids = set(sig_df.loc[sig_df["released"], "traj_id"])
suppressed_fraction = 1 - len(released_ids) / len(sig_df)
print(f"Suppressed {suppressed_fraction:.1%} of trajectories to reach k={K}")

Suppression is the fallback for traces that no generalization made common enough. Never publish suppressed trajectory IDs or a “withheld” marker — the mere fact that a path was too unique to release is itself disclosive.

Step 5 — Generalize and Emit the Release # permalink

# Each released trajectory is emitted as its generalized signature, using the
# cell centroid as the representative location — no original coordinate leaves
# the pipeline. Reproject centroids back to WGS84 for downstream consumers.
def centroid_lonlat(col: int, row: int) -> tuple[float, float]:
    """Return the WGS84 (lon, lat) centroid of a grid cell in the metric CRS."""
    x = minx + (col + 0.5) * CELL_SIZE
    y = miny + (row + 0.5) * CELL_SIZE
    pt = gpd.GeoSeries.from_xy([x], [y], crs=METRIC_CRS).to_crs("EPSG:4326")
    return float(pt.x.iloc[0]), float(pt.y.iloc[0])

out_rows = []
for traj_id in released_ids:
    for col, row, tbin in dict.fromkeys(sig[traj_id]):  # ordered, de-duplicated
        lon, lat = centroid_lonlat(col, row)
        # class_id groups indistinguishable traces; no uid is ever released.
        out_rows.append({"class_id": hash(sig[traj_id]), "lon": lon,
                         "lat": lat, "time_bin": tbin})

release = pd.DataFrame(out_rows)

The output carries a class_id shared by every trace in an equivalence class and never the original uid, so consumers can reconstruct group-level flows without any handle back to an individual.

Validation & Re-identification Testing # permalink

Anonymization is not complete until you have measured residual risk on the actual output.

Uniqueness and Neighbour-Count Audit # permalink

# Confirm the k guarantee empirically: every released class must have >= K members.
final_sizes = (
    release.groupby("class_id").size()  # rows per class ~ trace count proxy
)
assert (class_size[class_size >= K]).min() >= K, "A released class is below k"

# Uniqueness rate: fraction of trajectories that were unique before grouping.
unique_before = (class_size == 1).sum() / len(class_size)
print(f"Pre-anonymization unique trajectories: {unique_before:.1%}")

A high pre-anonymization uniqueness rate — routine for mobility data — is exactly why point-level masking is insufficient and why the class-size floor must be checked on the released signatures, not the raw traces. For a deeper treatment, see estimating uniqueness of mobility traces.

Re-identification Simulation # permalink

Model an adversary who holds a few known spatio-temporal points about a target — the classic “four points identify 95%” attack — and check whether those points still isolate a single released class:

def reidentification_rate(release: pd.DataFrame, n_known: int = 4,
                          trials: int = 1000, rng_seed: int = 0) -> float:
    """Fraction of simulated adversaries who isolate a unique class from
    n_known randomly chosen (cell, time-bin) observations of a target."""
    rng = np.random.default_rng(rng_seed)
    obs = release[["class_id", "lon", "lat", "time_bin"]]
    classes = obs["class_id"].unique()
    hits = 0
    for _ in range(trials):
        target = rng.choice(classes)
        known = obs[obs["class_id"] == target].sample(
            min(n_known, (obs["class_id"] == target).sum()), random_state=int(rng.integers(1e9))
        )
        # Which classes are consistent with ALL known observations?
        consistent = obs.merge(known[["lon", "lat", "time_bin"]],
                               on=["lon", "lat", "time_bin"])["class_id"].nunique()
        hits += consistent == 1
    return hits / trials

print(f"Re-identification rate: {reidentification_rate(release):.2%}")
# Target: at or below 1/k. A higher rate means classes are too distinctive.

If the simulated rate exceeds $1/k$, the generalization is too fine — increase cell size, widen time bins, or raise $k$. Adversaries who additionally reconstruct the road-constrained path require the countermeasures in defending against map-matching attacks, since map-matching can re-sharpen a generalized route back onto a unique street sequence.

Common Failure Modes & Gotchas # permalink

Grouping whole logs instead of segments. If you skip Step 2, each multi-day user log is one enormous, unique trajectory and every class collapses to size 1. Always segment into trip-scale sub-trajectories first.

Computing radii in degrees. A $\delta$ or cell size specified in degrees protects a rural northern user far less than an equatorial one. Do all metric operations in a UTM projection; degrees are for input and final output only.

Ignoring stay points. Long dwell times at a home or clinic dominate a trajectory’s identifiability even after the moving segments are generalized. Pair this workflow with stop-location and POI suppression so that sensitive stays are removed before grouping.

Persistent pseudonyms across releases. Reusing the same uid hash between publications lets an attacker join two k-anonymous releases and intersect the classes, collapsing k. Re-salt pseudonyms every release.

Temporal precision leakage. Releasing exact timestamps alongside generalized cells defeats the spatial generalization — a unique arrival time re-singles the trace. Bin time as aggressively as space, or apply temporal cloaking and time obfuscation.

Treating suppression as free. A high suppressed fraction $\phi$ removes precisely the outlying, most interesting movements, biasing any downstream analysis. Track $\phi$ and report it; if it exceeds your tolerance, the honest fix is often synthetic mobility data generation rather than ever-coarser bins.

Compliance Alignment # permalink

Because trajectory data is high-risk, GDPR Article 35 generally makes a data protection impact assessment mandatory. Record the selected parameters, the measured pre-anonymization uniqueness, the re-identification simulation rate, and the suppressed fraction; that package is the defensible evidence a regulator expects, and it links directly to the broader GDPR and CCPA compliance mapping for location data.

FAQ # permalink

What value of k should I use for trajectory k-anonymity?

Public releases of mobility data typically require $k \geq 5$; sensitive populations (health, minors, protected workers) commonly require $k \geq 10$. Because trajectories are high-dimensional, reaching a given $k$ demands far coarser spatial and temporal resolution than point-level k-anonymity grouping for location traces — expect cells of several hundred metres and time bins of 30 to 60 minutes.

Is trajectory k-anonymity the same as applying point k-anonymity per timestamp?

No. Point k-anonymity guarantees each individual location is shared by $k$ people, but an attacker who links consecutive released points can still isolate a unique path. Trajectory k-anonymity requires the entire ordered sequence to be indistinguishable among at least $k$ users — strictly stronger, and much harder to satisfy, which is why generalization and suppression are almost always needed together.

When should I publish synthetic trajectories instead of anonymizing real ones?

Choose synthetic replacement when you must publish fine-resolution individual paths and no grouping reaches an acceptable $k$ without destroying utility. Synthetic generation severs the one-to-one link to real individuals entirely, whereas k-anonymity and generalization retain a transformed version of real traces and stay vulnerable to auxiliary-information attacks.

Does trajectory generalization satisfy GDPR anonymization?

It can, when the generalized output is no longer reasonably re-identifiable given available auxiliary data, per Recital 26. Generalization alone rarely suffices for long or distinctive trajectories; combine it with a documented $k$ threshold, suppression of unique segments, and a re-identification test recorded in your data protection impact assessment.

Related # permalink

• Implementing Trajectory k-Anonymity with scikit-mobility — a focused, runnable build of the grouping step in this guide
• Synthetic Mobility Data Generation — replace real traces entirely when grouping cannot preserve utility
• Stop-Location & POI Suppression — remove sensitive stays before grouping
• Temporal Cloaking & Time Obfuscation — bin and shift timestamps so timing does not re-single a trace
• Re-identification Risk Assessment for Geospatial Datasets — measure density and uniqueness before choosing parameters

← Back to Trajectory & Mobility Data Privacy