Spatial Privacy & Anonymization Engineering

Detecting Stay-Points with DBSCAN for Suppression

Run DBSCAN per user on projected coordinates with eps set to the roaming radius and min_samples derived from the sampling rate, then keep only the clusters whose temporal span clears the dwell threshold. The density parameters have to come from the logger’s cadence, because DBSCAN counts points and a stay-point is defined by time.

Core Calculation permalink

DBSCAN forms a cluster around any point with at least min_samples neighbours inside radius eps. Applied to a GPS trace, that finds spatial density — which is what a dwell produces, but also what a slow crawl through traffic produces.

The bridge between the two is the sampling rate. If the logger emits one fix every Δs\Delta_s seconds and the stay-point definition requires a dwell of at least tmin⁡t_{\min}, then a genuine stay contains at least

min_samples=⌈tmin⁡Δs⌉\texttt{min\_samples} = \left\lceil \frac{t_{\min}}{\Delta_s} \right\rceil

points, and eps is the roaming radius dmax⁡d_{\max} directly. Choosing min_samples independently of Δs\Delta_s is the error that makes the detector behave differently on two datasets that describe the same behaviour.

DBSCAN alone is not sufficient, because it has no notion of time. A cluster it returns may be one 40-minute visit or four 10-minute visits on four different days at the same café. The temporal split is a second pass over each cluster’s timestamps.

Worked numeric example permalink

A logger at Δs=30\Delta_s = 30 s, roaming radius dmax⁡=150d_{\max} = 150 m, dwell threshold tmin⁡=10t_{\min} = 10 min:

min_samples=⌈600/30⌉=20,eps=150 m\texttt{min\_samples} = \lceil 600 / 30 \rceil = 20, \qquad \texttt{eps} = 150\ \mathrm{m}

Now suppose a second dataset from a battery-saving client samples at Δs=120\Delta_s = 120 s. Re-using min_samples = 20 would demand a 40-minute dwell and miss every clinic visit. The correct value is ⌈600/120⌉=5\lceil 600/120 \rceil = 5.

Python Implementation permalink

from __future__ import annotations

import math
import geopandas as gpd
import numpy as np
import pandas as pd
from sklearn.cluster import DBSCAN

def detect_stay_points(
    trace: gpd.GeoDataFrame,
    roaming_radius_m: float = 150.0,
    dwell_min_s: float = 600.0,
    max_gap_s: float = 900.0,
) -> pd.DataFrame:
    """Per-user stay-points from a GPS trace, split back into separate visits.

    DBSCAN finds spatial density; a stay-point is defined by dwell, so the
    density parameters are derived from the trace's own sampling interval and a
    second pass splits each cluster on temporal gaps.

    Args:
        trace: projected metric CRS, columns `user_id`, `t` (epoch seconds).
        roaming_radius_m: maximum spread of a single stay — DBSCAN's eps.
        dwell_min_s: minimum duration for a run of fixes to count as a stay.
        max_gap_s: a gap longer than this inside a cluster starts a new visit.
    """
    if not trace.crs or not trace.crs.is_projected:
        raise ValueError("project to a metric CRS before clustering")

    visits = []
    for uid, grp in trace.sort_values("t").groupby("user_id"):
        if len(grp) < 2:
            continue
        # Median inter-fix interval for THIS user, not a global constant.
        dt = float(np.median(np.diff(grp["t"].to_numpy())))
        min_samples = max(2, math.ceil(dwell_min_s / max(dt, 1.0)))

        xy = np.column_stack([grp.geometry.x, grp.geometry.y])
        labels = DBSCAN(eps=roaming_radius_m, min_samples=min_samples).fit_predict(xy)

        for lab in set(labels) - {-1}:
            sel = grp[labels == lab].sort_values("t")
            t = sel["t"].to_numpy()
            # Split the cluster wherever the device left and came back later.
            breaks = np.flatnonzero(np.diff(t) > max_gap_s) + 1
            for part in np.split(np.arange(len(t)), breaks):
                span = float(t[part[-1]] - t[part[0]])
                if span < dwell_min_s:
                    continue                     # a pass-through, not a stay
                seg = sel.iloc[part]
                visits.append({
                    "user_id": uid,
                    "x": float(seg.geometry.x.mean()),
                    "y": float(seg.geometry.y.mean()),
                    "t_start": float(t[part[0]]),
                    "t_end": float(t[part[-1]]),
                    "dwell_s": span,
                    "n_fixes": int(len(part)),
                    "sampling_s": dt,
                })
    return pd.DataFrame(visits)

Verification permalink

def verify_stay_points(visits: pd.DataFrame, dwell_min_s: float,
                       roaming_radius_m: float) -> dict:
    """Confirm the detector's own invariants before anything downstream trusts it."""
    return {
        "min_dwell_s": float(visits["dwell_s"].min()),
        "dwell_floor_respected": bool((visits["dwell_s"] >= dwell_min_s).all()),
        "median_fixes_per_visit": float(visits["n_fixes"].median()),
        "visits_per_user_median": float(visits.groupby("user_id").size().median()),
        "suspiciously_long": int((visits["dwell_s"] > 16 * 3600).sum()),
    }

suspiciously_long is the field worth watching. A single “visit” spanning more than sixteen hours usually means two clusters were merged because max_gap_s was too generous, or that the device was stationary overnight and the home cluster swallowed the following morning. Both distort the home and workplace inference that runs downstream.

The second check is against labelled ground truth if you have any: a sample of traces where the real visits are known. Report recall on short visits specifically, because those are the sensitive ones and the ones the parameters miss first.

Edge Cases & Adjustments permalink

  • Multi-storey and indoor locations. GPS drifts indoors, so a single visit can spread well beyond the roaming radius and fragment into several clusters. Raise eps for indoor-heavy datasets or merge clusters whose centroids fall within one radius of each other before the temporal pass.
  • Traffic jams. A stationary vehicle in congestion produces a dense cluster indistinguishable from a stay on geometry alone. Filter candidate stays by road proximity, or require that the dwell exceed the local congestion’s typical duration.
  • Varying cadence within one user. A device that switches between foreground and background modes has no single Δs\Delta_s. Using the median as above is robust; using the mean is not, because a few long gaps dominate it.
  • max_gap_s too large. A generous gap merges a lunch visit with the afternoon return to the office. Set it below the shortest realistic absence, typically 10–20 minutes.
  • Very sparse traces. Below a few fixes per hour, no density parameter recovers stays reliably. Record the sampling rate per visit — the implementation returns it — so downstream consumers can filter on detection confidence rather than assuming uniform quality.

Tuning Against a Labelled Sample permalink

Parameter derivation gets the detector into the right region; only a labelled sample tells you whether it is right.

Collect a few dozen traces where the true visits are known — a volunteer diary, a staff test, or a synthetic trace generated with known stops — and report recall on short visits specifically. Recall on all visits is dominated by long dwells at home and work, which every parameter setting finds, and it therefore stays high while the detector misses exactly the visits the suppression pipeline exists to protect.

Report precision too, but weight it lightly. A false positive is a stay that gets generalised when it did not need to be, which costs a little utility. A false negative is a sensitive visit that ships at full precision. The asymmetry is large enough that a detector tuned to over-detect and let the sensitivity scoring sort out the candidates is usually the right operating point.

Two failure patterns show up repeatedly in this exercise. The first is a cluster of missed short visits at one location, which almost always means the roaming radius is too tight for indoor GPS drift at that building. The second is a set of false stays along one corridor, which means congestion is being read as dwell and the detector needs a road-proximity or minimum-duration filter on that segment.

Whatever the sample says, record the parameters and the recall figure together in the release record. A stay-point detector is the input to every downstream suppression decision, and a suppression claim is only as good as the detection recall behind it.

What the Detector Hands Downstream permalink

The output of this step is not a list of places; it is a list of visits, and the difference decides what the rest of the pipeline can do.

A visit carries a centroid, an interval, a dwell duration and a fix count. The centroid feeds the POI join that assigns a category. The dwell feeds the sensitivity score. The interval feeds the temporal checks, and the fix count is the confidence signal that lets a downstream consumer discount a visit inferred from three pings. Dropping any of the four saves a column and removes an input that something later needs.

Most importantly, the number of visits to a location is itself a signal. Three separate visits to a clinic is a materially different disclosure from one long one, and a detector that merges recurring visits into a single stay hides exactly the pattern that distinguishes an anchor from an errand.

FAQ permalink

Why DBSCAN rather than the classic sequential stay-point algorithm?

The sequential algorithm walks the trace in order and is the more faithful implementation of the definition. DBSCAN is used here because it handles out-of-order and duplicated fixes without preprocessing, and because it naturally groups repeat visits to the same place, which the temporal pass then splits. Either is defensible; the parameter derivation is the same.

Should clustering run per user or across all users?

Per user, always. A cross-user cluster is a popular place, not a stay-point, and mixing the two produces “visits” belonging to nobody.

What if the trace has no user identifier?

Then stay-point detection is not available, and neither is the suppression that depends on it. Detecting dwell requires knowing which fixes belong to the same device.

Does the detector need to be exact?

It needs high recall on sensitive short visits and can tolerate false positives, because a wrongly detected stay is generalised rather than published. Tune the parameters to over-detect and let the sensitivity scoring decide what to do with each candidate.

← Back to Stop-Location & POI Suppression

Related topics

Suppressing Home and Work Anchors in GPS Logs

How to infer the residential and workplace anchors from dwell schedules, suppress them along with the approach geometry...