# Mixing and $C\\!P$ violation in Charm decays at LHCb

Roberto Ribatti†
on behalf of the LHCb collaboration  †Scuola Normale Superiore and INFN
Sezione di Pisa, Pisa, Italy

###### Abstract

Two measurements of mixing and $C\\!P$ violation in charm decays performed at
the LHCb experiment are presented. The former is a measurement of the mixing
observable $y_{C\\!P}-y_{C\\!P}^{{K}{\pi}}$ in two-body ${D}^{0}$ decays,
while the latter is a search for direct $C\\!P$ violation in
${D}^{+}_{(s)}\rightarrow\eta^{(\prime)}{{\pi}^{+}}$ decays.

##  I Introduction

In the Standard Model (SM), mixing and $C\\!P$ violation in charm are highly
suppressed, due to the smallness of the CKM matrix elements involved in these
processes and to the GIM mechanism. Measurements of mixing and $C\\!P\\!V$ in
charm provide good sensitivity to beyond SM operators that couples to up-type
quarks only.

The ${D}^{0}$ mass eigenstates can be written as linear combinations of
flavour eigenstates $|D_{1,2}\rangle=p|{{D}^{0}}\rangle\pm q|{{\kern
1.79993pt\overline{\kern-1.79993ptD}}{}^{0}}\rangle$, where $p$ and $q$ are
complex parameters. Oscillations are characterized by two parameters: the
differences in mass, $x\equiv(m_{1}-m_{2})/\Gamma$, and in decay width,
$y\equiv(\Gamma_{1}-\Gamma_{2})/2\Gamma$, between the $D^{0}$ mass eigenstates
(here $\Gamma$ is the average decay width of the ${D}^{0}$ mass eigenstates).
If $C\\!P$ is violated, then the oscillation probabilities for ${D}^{0}$ and
${\kern 1.79993pt\overline{\kern-1.79993ptD}}{}^{0}$ mesons can differ.

In recent years significant progress has been made in this research field,
mainly due to the large samples of charmed hadron decays collected by the LHCb
experiment. The first observation of a non-zero value of the $y$ parameter
dates back to 2010 by BaBar and Belle collaborations HFLAV:2010pgm  and today
we are approaching a 3% relative precision on its world-averaged value
LHCb:2021dcr . The first observation of a non-zero value of $x$, instead, was
achieved only in 2021 from the LHCb collaboration LHCb:2021ykz . Moreover, in
2019 the LHCb collaboration announced the first observation of $C\\!P$
violation in charm decays LHCb:2019hro , achieved looking at the difference of
the time-integrated $C\\!P$ asymmetries of
${{D}^{0}}\\!\rightarrow{{K}^{+}}{{K}^{-}}$ and
${{D}^{0}}\\!\rightarrow{{\pi}^{+}}{{\pi}^{-}}$ decays, $\Delta
A_{{C\\!P}}\equiv
A_{{C\\!P}}({{K}^{+}}{{K}^{-}})-A_{{C\\!P}}({{\pi}^{+}}{{\pi}^{-}})$. However,
the large theoretical uncertainty on nonperturbative QCD effects, which might
contribute to enhance $C\\!P$ violation, does not allow to unequivocally
establish if this observation is compatible or not with the SM. Further
measurements are crucial to shed light on $C\\!P$ violation theoretical
interpretation in the up-type quarks sector.

In these proceedings, two recent LHCb measurements of mixing and $C\\!P$
violation in charm decays are presented: a measurement of the mixing
observable $y_{C\\!P}-y_{C\\!P}^{{K}{\pi}}$ in two-body ${D}^{0}$ meson decays
and a search for direct $C\\!P$ violation in
${D}^{+}_{(s)}\rightarrow\eta^{(\prime)}{{\pi}^{+}}$ decays.

##  II Measurement of the charm mixing parameter $y_{C\\!P}$ with
${{D}^{0}}\rightarrow h^{+}h^{-}$ decays

The $y_{C\\!P}$ mixing observable is defined based on ${{D}^{0}}$ two-body
decay rates. As shown in Fig. 1, the self-conjugate final states
${{D}^{0}}\rightarrow f$, with $f={{K}^{-}}{{K}^{+}}$ or
${{\pi}^{-}}{{\pi}^{+}}$, undergo a Cabibbo-suppressed decay either directly
of after mixing, while the ${{K}^{-}}{{\pi}^{+}}$ final state is dominated by
the Cabibbo-favoured amplitude, since the contribution following mixing is
suppressed by the subsequent doubly Cabibbo-suppressed decay.

Figure 1: Sketches of the interfering amplitudes of ${D}^{0}$ two-body decays.

The time-dependent decay rates can be described by exponential functions with
an effective decay width. The non-zero value of $y$ introduces a shift between
the two decay modes. The departure from unity of the ratio of the effective
decay widths of ${{D}^{0}}\rightarrow f$ and
${{D}^{0}}\rightarrow{{K}^{-}}{{\pi}^{+}}$ is the target observable:

$\displaystyle\frac{\Gamma({{D}^{0}}\rightarrow f)+\Gamma({{\kern
1.79993pt\overline{\kern-1.79993ptD}}{}^{0}}\rightarrow
f)}{\Gamma({{D}^{0}}\rightarrow{{K}^{-}}{{\pi}^{+}})+\Gamma({{\kern
1.79993pt\overline{\kern-1.79993ptD}}{}^{0}}\rightarrow{{K}^{+}}{{\pi}^{-}})}-1\simeq$
(1) $\displaystyle\hskip 113.81102pt\simeq
y_{{C\\!P}}^{f}-y_{{C\\!P}}^{{K}{\pi}}.$

At the current experimental sensitivity, final-state dependent contributions
and $C\\!P$ violation effects can be neglected, hence $y_{{C\\!P}}^{f}$ is
equal to $y$. The correction term $y_{C\\!P}^{{K}{\pi}}$ is approximately
equal to $\sqrt{R_{D}}y\approx 6\%\,y$, Pajero:2021jev  where $R_{D}$ is the
ratio of the branching fractions of the doubly Cabibbo-suppressed
${{D}^{0}}\rightarrow{{K}^{+}}{{\pi}^{-}}$ decay to the Cabibbo-favoured
${{D}^{0}}\rightarrow{{K}^{-}}{{\pi}^{+}}$ decay.

The observable of interest is measured through an exponential fit to the ratio

$\displaystyle R^{f}(t)=\frac{N({{D}^{0}}\rightarrow
f,t)}{N({{D}^{0}}\rightarrow{{K}^{-}}{{\pi}^{+}},t)}\propto$ (2)
$\displaystyle\propto
e^{-(y_{{C\\!P}}^{f}-y_{{C\\!P}}^{{K}{\pi}})t/\tau_{{{D}^{0}}}}\frac{\epsilon(f,t)}{\epsilon({{K}^{-}}{{\pi}^{+}},t)},$

where $\tau_{{{D}^{0}}}$ is the lifetime of the ${{D}^{0}}$ meson and
$\epsilon(X)$ is the time-dependent efficiency of the $X$ decay mode.

This measurement is performed using proton-proton ($pp$) collision collected
at the LHCb experiment at a centre-of-mass energy of 13 TeV during Run 2
(2015–2018), corresponding to an integrated luminosity of 6$\text{\,fb}^{-1}$.
The ${D}^{0}$ meson is required to come from a
${{D}^{*+}}\rightarrow{{D}^{0}}{{\pi}^{+}}$ decay, such that the flavour of
the ${{D}^{0}}$ is determined from the charge of the slow pion.

### Efficiency equalization

Trigger requirements are applied to the ${D}^{0}$ daughters tracks, on
kinematic observables such as momentum and pseudorapidity. Applying these
requirement to different final states, with different kinematic distributions,
introduces discrepancies between the time-dependent efficiency of these final
states. In order to equalize these efficiencies, a procedure called kinematic
matching is applied. It consists in computing new kinematic variables, called
matched variables, designed to have the same distribution for the ${D}^{0}$
$\rightarrow$ $f$ decays and ${D}^{0}$ $\rightarrow$ ${K}^{-}$ ${\pi}^{+}$
decay, so that if a selection on these variables is applied, the efficiency is
equal for both final states. To compute the matched kinematic variables for a
${D}^{0}$ $\rightarrow$ ${K}^{-}$ ${K}^{+}$ decay, the momentum of the
daughter particles in the ${D}^{0}$ centre-of-mass frame, which is
791$\text{\,Me\kern-1.00006ptV\\!/}c$ for a ${D}^{0}$ $\rightarrow$ ${K}^{-}$
${K}^{+}$ decay, is changed to 861$\text{\,Me\kern-1.00006ptV\\!/}c$ (the
value for a ${D}^{0}$ $\rightarrow$ ${K}^{-}$ ${\pi}^{+}$ decay).

To remove the effect of the trigger requirements, tighter requirements are
applied on the matched kinematic variables. Figure 2 shows an example of how
the new thresholds are determined to ensure that both ${D}^{0}$ $\rightarrow$
${K}^{-}$ ${K}^{+}$ and ${D}^{0}$ $\rightarrow$ ${K}^{-}$ ${\pi}^{+}$ decays
are selected with the same efficiency.

Figure 2: Matched versus original transverse momenta of a kaon from a
${D}^{0}$ $\rightarrow$ ${K}^{-}$ ${K}^{+}$ decay. Candidates below the red
line are rejected. Figure from ref. LHCb:2022gnc .

The different interaction with the matter of kaons compared to pions, as well
as particle identification requirements, produce efficiency discrepancies that
cannot be removed by the kinematic matching. To remove these residual
discrepancies, the $p$, $p_{T}$ and $\eta$ distributions of the ${{D}^{*+}}$
mesons of ${{D}^{0}}\rightarrow f$ decays are weighted to the corresponding
distributions of ${{D}^{0}}\rightarrow{{K}^{-}}{{\pi}^{+}}$ decay, using a
gradient-boosted reweighting algorithm from the hep_ml library
Rogozhnikov:2016bdp .

This efficiency equalization is validated with simulated samples and also on
data, through a cross-check observable,

$\displaystyle
R^{CC}(t)=\frac{N({{D}^{0}}\rightarrow{{\pi}^{-}}{{\pi}^{+}},t)}{N({{D}^{0}}\rightarrow{{K}^{-}}{{K}^{+}},t)}\propto$
(3) $\displaystyle\propto
e^{-y^{CC}_{{C\\!P}}t/\tau_{{{D}^{0}}}}\frac{\epsilon({{\pi}^{-}}{{\pi}^{+}},t)}{\epsilon({{K}^{-}}{{K}^{+}},t)},$

where $y^{CC}_{{C\\!P}}$ is expected to be zero in the SM and is measured to
be $y^{CC}_{{C\\!P}}=(-0.44\pm 0.53)\times 10^{-3}$.

### Yield determination and main backgrounds

The combinatorial background, mainly due to random slow pion, is the main
background in the data sample. In order to disentangle the signal yield from
this background, a binned $\chi^{2}$ fit is performed, in bins of ${D}^{0}$
decay time, to the $\Delta m=m(h^{-}h^{+}\pi^{+}_{\text{tag}})-m(h^{-}h^{+})$
observable, where $m(h^{-}h^{+}\pi^{+}_{\text{tag}})$ is the mass of the
${{D}^{*+}}$ candidate and $m(h^{-}h^{+})$ is the mass of the ${D}^{0}$
candidate. Most of the uncertainty related to the ${D}^{0}$ mass resolution is
cancelled in the subtraction, considerably improving the mass resolution. The
signal model consists of the sum of three Gaussian and of a Johnson SU
Johnson:1949  functions, while the combinatorial background is modelled with
this empirical function

$\displaystyle\mathcal{P}_{\text{BKG}}(\Delta m|m_{0},\alpha)\equiv$ (4)
$\displaystyle\equiv\frac{1}{\mathcal{I}_{B}}\cdot\sqrt{\frac{\Delta
m^{2}}{m_{0}^{2}}-1}\cdot\exp\left(-\alpha\left(\frac{\Delta
m^{2}}{m_{0}^{2}}-1\right)\right).$

The signal yields, integrated over all decay-time bins, amount to 70 million,
18 million, and 6 million decays, respectively for the ${D}^{0}$ $\rightarrow$
${K}^{-}$ ${\pi}^{+}$, ${D}^{0}$ $\rightarrow$ ${K}^{-}$ ${K}^{+}$ and
${D}^{0}$ $\rightarrow$ ${\pi}^{-}$ ${\pi}^{+}$ decay channels.

The second main background contribution comes from ${D}^{*+}$ mesons that are
not produced at the interaction vertex, but that rather come from a ${B}^{0}$
or ${{B}^{+}}$ decay. The reconstructed decay time of those candidates is
biased toward larger values, diluting the mixing effects. To reduce this
background, a requirement on the ${D}^{0}$ impact parameter with respect to
the its interaction vertex, is applied. The fraction of residual background is
fitted with simulated templates in the 2D-variables space of the ${D}^{0}$
impact parameter and decay time. Then the decay-time bias from the residual
background is estimated with the LHCb simulation, and subtracted.

Figure 3: Corrected values of $R^{{\pi}{\pi}}(t)$ (top) and $R^{{K}{K}}(t)$
(bottom) for the full dataset with the fit results overlaid. Figure from ref.
LHCb:2022gnc .

### Final results

The parameters are determined from a $\chi^{2}$ fit to the time-dependent
$R^{f}(t)$ ratios. Figure 3 shows the distributions of $R^{f}(t)$ for the full
dataset, with the fit result overlaid. The final results are

$\displaystyle y_{C\\!P}^{{\pi}{\pi}}-y_{C\\!P}^{{K}{\pi}}$
$\displaystyle=(6.57\pm 0.53\pm 0.16)\times 10^{-3}$ $\displaystyle
y_{C\\!P}^{{K}{K}}-y_{C\\!P}^{{K}{\pi}}$ $\displaystyle=(7.08\pm 0.30\pm
0.14)\times 10^{-3},$

where the first uncertainty is statistical, while the second is systematic.
Accounting for correlations among the systematic uncertainties, the
combination is

$y_{C\\!P}-y_{C\\!P}^{{K}{\pi}}=(6.96\pm 0.26\pm 0.13)\times 10^{-3}.$

This measurement is statistically limited and it improves the world average by
a factor 4.

##  III Measurement of $C\\!P$ asymmetries in
$D_{(s)}^{+}\rightarrow\eta^{(\prime)}\pi^{+}$ decays

The goal of this analysis is the measurement of the time-integrated $C\\!P$
asymmetry of the singly Cabibbo-suppressed ${D}^{+}$ $\rightarrow$
$\eta^{(\prime)}$${\pi}^{+}$ decay, while simultaneously measuring the
Cabibbo-favoured ${D}^{+}_{s}$ $\rightarrow$ $\eta^{(\prime)}$${\pi}^{+}$
decay. Singly Cabibbo-suppressed decay channels are of particular interest
because $C\\!P$ violation may manifest due to the interference of tree level
amplitudes. No evidence for $C\\!P$ violation has been observed in these decay
channels by the CLEO CLEO:2009fiz ; CLEO:2013bae , Belle Belle:2011tmj ;
Belle:2021ygw  and LHCb LHCb:2021rou ; LHCb:2017lea  collaborations.

Also this measurement is performed using $pp$-collision data collected at the
LHCb experiment at a centre-of-mass energy of 13 TeV during Run 2 (2015-2018),
corresponding to an integrated luminosity of 6$\text{\,fb}^{-1}$. Both $\eta$
and $\eta^{\prime}$ mesons are reconstructed in the $\gamma$ ${\pi}^{-}$
${\pi}^{+}$ final state. The two charged pions allow the decay vertex to be
reconstructed, which is crucial to reduce the combinatorial background. The
$C\\!P$ asymmetry is defined as

$\mathcal{A}^{{C\\!P}}(D^{+}_{(s)}\rightarrow
f^{+})\equiv\frac{\Gamma(D^{+}_{(s)}\rightarrow
f^{+})-\Gamma(D^{-}_{(s)}\rightarrow f^{-})}{\Gamma(D^{+}_{(s)}\rightarrow
f^{+})+\Gamma(D^{-}_{(s)}\rightarrow f^{-})},$ (5)

where $\Gamma$ is the partial decay width to the final state of interest $f$.
For each of the analysed final states, the measured experimental observable is
the raw asymmetry,

$\mathcal{A}^{\text{raw}}(D^{+}_{(s)}\rightarrow
f^{+})\equiv\frac{N(D^{+}_{(s)}\rightarrow f^{+})-N(D^{-}_{(s)}\rightarrow
f^{-})}{N(D^{+}_{(s)}\rightarrow f^{+})+N(D^{-}_{(s)}\rightarrow f^{-})},$ (6)

where $N$ refer to the measured yield. For small asymmetries, a first-order
approximation can be used:

$\displaystyle\mathcal{A}^{\text{raw}}$ $\displaystyle(D^{+}_{(s)}\rightarrow
f^{+})\simeq$ (7)
$\displaystyle\simeq\mathcal{A}^{{C\\!P}}(D^{+}_{(s)}\rightarrow
f^{+})+\mathcal{A}^{\text{prod}}(D^{+}_{(s)})+\mathcal{A}^{\text{det}}(f^{+}).$

Therefore, to extract the $C\\!P$ asymmetry value from the raw asymmetry, we
have to correct for the production asymmetry and the detection asymmetry. The
production asymmetry is defined as

$\mathcal{A}^{\text{prod}}(D^{+}_{(s)})\equiv\frac{\sigma(D^{+}_{(s)})-\sigma(D^{-}_{(s)})}{\sigma(D^{+}_{(s)})+\sigma(D^{-}_{(s)})},$
(8)

where $\sigma(D^{\pm}_{(s)})$ is the production cross-section of the
$D^{+}_{(s)}$ and $D^{-}_{(s)}$ mesons, which differ at the LHC, because of
the $C\\!P$ asymmetric initial state, $pp$. The detection asymmetry is defined
as

$\mathcal{A}^{\text{det}}(f^{+})\equiv\frac{\epsilon(f^{+})-\epsilon(f^{-})}{\epsilon(f^{+})+\epsilon(f^{-})},$
(9)

where $\epsilon(f^{\pm})$ is the detection efficiency of the final state
$f^{+}$ and $f^{-}$. These two values can differ due to the different
interaction with matter of particles and antiparticles. In our case of study,
the detection asymmetry is fully due to the pion in the
$D^{\pm}_{(s)}\rightarrow\eta^{(\prime)}{{\pi}^{\pm}}$ decay, because the
$\eta^{(\prime)}$ final state, ${\gamma}{{\pi}^{-}}{{\pi}^{+}}$ is $C\\!P$
symmetric. In order to subtract these nuisance asymmetries, the raw asymmetry
of the control channels are subtracted. These control channels have identical
contributions from production and detection asymmetries, but have a
negligible, or precisely known, $C\\!P$ asymmetry. The control samples consist
of the Cabibbo-favoured ${{D}^{+}_{s}}\rightarrow\phi{{\pi}^{+}}$ decays,
where $\mathcal{A}^{{C\\!P}}$ is assumed negligible in the SM, and the singly
Cabibbo-suppressed ${{D}^{+}}\rightarrow\phi{{\pi}^{+}}$ decay, where
$\mathcal{A}^{{C\\!P}}({{D}^{+}}\rightarrow\phi{{\pi}^{+}})=(0.5\pm 5.1)\times
10^{-4}$ has been previously measured by the LHCb collaboration LHCb:2019dwr .
The $\phi$ meson is reconstructed in the self-coniugate ${{K}^{-}}{{K}^{+}}$
final state.

Figure 4: Distributions of $m(\eta^{(\prime)}{{\pi}^{+}})$ (left) and
$m(\eta^{(\prime)}{{\pi}^{+}})$ (right) for candidates with
$m({\gamma}{{\pi}^{-}}{{\pi}^{+}})$ in the range
936–976$\text{\,Me\kern-1.00006ptV\\!/}c^{2}$ (top) and
526–570$\text{\,Me\kern-1.00006ptV\\!/}c^{2}$ (bottom). The fit results are
superimposed. Figure from ref. LHCb:2022pxf .

Figure 5: Distributions of $m({\gamma}{{\pi}^{-}}{{\pi}^{+}})$ for
$D^{\pm}_{(s)}\rightarrow\eta^{\prime}{{\pi}^{\pm}}$ (top) and
$D^{\pm}_{(s)}\rightarrow\eta{{\pi}^{\pm}}$ (bottom). The fit results are
superimposed. Figure from ref. LHCb:2022pxf .

The experimental observables are

$\displaystyle\mathcal{A}^{C\\!P}$
$\displaystyle({{D}^{+}}\rightarrow\eta^{(\prime)}{{\pi}^{+}})=$ (10)
$\displaystyle=\mathcal{A}^{\text{raw}}({{D}^{+}}\rightarrow\eta^{(\prime)}{{\pi}^{+}})-\mathcal{A}^{\text{raw}}({{D}^{+}}\rightarrow\phi{{\pi}^{+}})+$
$\displaystyle+\mathcal{A}^{C\\!P}({{D}^{+}}\rightarrow\phi{{\pi}^{+}}),$
$\displaystyle\mathcal{A}^{C\\!P}$
$\displaystyle({{D}^{+}_{s}}\rightarrow\eta^{(\prime)}{{\pi}^{+}})=$ (11)
$\displaystyle=\mathcal{A}^{\text{raw}}({{D}^{+}_{s}}\rightarrow\eta^{(\prime)}{{\pi}^{+}})-\mathcal{A}^{\text{raw}}({{D}^{+}_{s}}\rightarrow\phi{{\pi}^{+}}).$

### Determination of the raw asymmetry

The main background in the sample is combinatorial background. In order to
determine the raw asymmetry, signal yields need to be extracted and
disentangled from this background. To do this, a binned maximum-likelihood fit
is performed simultaneously in the 3D variable space
$[m(\eta^{(\prime)}{{\pi}^{+}}),m(\eta^{(\prime)}{{\pi}^{-}}),m({\gamma}{{\pi}^{-}}{{\pi}^{+}})]$.
Both the signal and combinatorial background are modeled with empirical
functions. The ${D}^{\pm}_{s}$ and ${D}^{\pm}$ signal models are Johnson
SUJohnson:1949  functions in the $m(\eta^{(\prime)}{{\pi}^{\pm}})$ variable. A
quadratic dependence on $m({\gamma}{{\pi}^{-}}{{\pi}^{+}})$ is allowed for the
mean and the width, while $\Delta m\equiv m({{D}^{+}_{s}})-m({{D}^{+}})$
linearly depends on it. The two Johnson SU parameters that mainly determine
the asymmetry and kurtosis of the distribution are shared between
${{D}^{+}_{s}}$ and ${{D}^{+}}$ and between positively and negatively charged
candidates. The model for the combinatorial background is a third-order
Chebyshev polynomial in the $m(\eta^{(\prime)}{{\pi}^{\pm}})$ variable,
independent in each bin of $m({\gamma}{{\pi}^{-}}{{\pi}^{+}})$ and for
positively and negatively charged candidates. Only for the
$D^{+}_{(s)}\rightarrow\eta^{\prime}{{\pi}^{+}}$ decay, a further background
is considered, coming from
${D}^{+}_{(s)}\rightarrow\phi(\rightarrow{{\pi}^{-}}{{\pi}^{+}}{{\pi}^{0}}){{\pi}^{+}}$
decays where the ${\pi}^{0}$ is misreconstructed as a photon. The shape of
this background is fixed from simulation. Figures 4 and 5 show the
$m(\eta^{(\prime)}{{\pi}^{\pm}})$ and $m({\gamma}{{\pi}^{-}}{{\pi}^{+}})$
distributions with the fit results superimposed.

### Control channel yields extraction

Due to the absence of neutral particles, the control channels have much less
background. To correctly subtract nuisance asymmetries, the kinematics
distribution (transverse momentum and pseudorapidity of $D^{+}_{(s)}$ and
tagging pion) of the control channels have to be weighted to those of the
signal channels in the The small background component is subtracted using the
sPlot technique Pivk:2004ty , using $m(\eta^{(^{\prime}){{\pi}^{+}}})$ as
discriminating variable.

### Final results

The final value of $\mathcal{A}^{{C\\!P}}$ after the combination with previous
LHCb measurements using different $\eta$ final states LHCb:2021rou  or
independent data samples LHCb:2017lea  are:

$\displaystyle\mathcal{A}^{C\\!P}({{D}^{+}}\rightarrow\eta{{\pi}^{+}})$
$\displaystyle=(0.13\pm 0.50\pm 0.18)\%$
$\displaystyle\mathcal{A}^{C\\!P}({{D}^{+}}\rightarrow\eta^{\prime}{{\pi}^{+}})$
$\displaystyle=(0.43\pm 0.17\pm 0.10)\%$
$\displaystyle\mathcal{A}^{C\\!P}({{D}^{+}_{s}}\rightarrow\eta{{\pi}^{+}})$
$\displaystyle=(0.48\pm 0.42\pm 0.17)\%$
$\displaystyle\mathcal{A}^{C\\!P}({{D}^{+}_{s}}\rightarrow\eta^{\prime}{{\pi}^{+}})$
$\displaystyle=(-0.04\pm 0.11\pm 0.09)\%,$

where the first uncertainty is statistical, and the second is systematic. The
results are compatible with the conservation of the $C\\!P$ symmetry. For the
${{D}^{+}}\rightarrow\eta{{\pi}^{+}}$,
${{D}^{+}}\rightarrow\eta^{\prime}{{\pi}^{+}}$ and
${{D}^{+}_{s}}\rightarrow\eta^{\prime}{{\pi}^{+}}$ decay channels, this is the
most precise measurement to date.

##  IV Future prospects

We have just barely started to approach the SM upper limits for $C\\!P$
violation in charm decays. LHCb–Upgrade I started in 2022 and over 23
(50)$\text{\,fb}^{-1}$ of integrated luminosity are expected to be collected
by the end of Run 3 (4) in 2025 (2032). Moreover, the new LHCb data
acquisition and trigger system will help to increase the reconstruction
efficiency per $\text{\,fb}^{-1}$, in particular for hadronic charm decays
Bediaga:2018lhg . This large amount of data will allow for a significant
improvement in the accuracy of mixing and $C\\!P$-violation measurements in
the charm sector.

## References

  * (1) D. Asner et al. [HFLAV group], arXiv:1010.1589.
  * (2) Y. Amhis et al. [HFLAV group], arXiv:2206.07501.
  * (3) R. Aaij et al. [LHCb collaboration], JHEP 12, 141 (2021), arXiv:2110.02350.
  * (4) R. Aaij et al. [LHCb collaboration], Phys. Rev. Lett. 127, no.11, 111801 (2021), arXiv:2106.03744.
  * (5) R. Aaij et al. [LHCb collaboration], Phys. Rev. Lett. 122, no.21, 211803 (2019), arXiv:1903.08726.
  * (6) T. Pajero and M. J. Morello, JHEP 03, 162 (2022), arXiv:2106.02014.
  * (7) R. Aaij et al. [LHCb collaboration], Phys. Rev. D 105, no.9, 092013 (2022), arXiv:2202.09106.
  * (8) A. Rogozhnikov, J. Phys. Conf. Ser. 762, no.1, 012036 (2016).
  * (9) N. L. Johnson, Biometrika 36, 149 (1949).
  * (10) H. Mendez et al. [CLEO collaboration], Phys. Rev. D 81, 052013 (2010), arXiv:0906.3198.
  * (11) P. U. E. Onyisi et al. [CLEO collaboration], Phys. Rev. D 88, no.3, 032009 (2013), arXiv:1306.5363.
  * (12) E. Won et al. [Belle collaboration], Phys. Rev. Lett. 107, 221801 (2011). arXiv:1107.0553.
  * (13) Y. Guan et al. [Belle collaboration], Phys. Rev. D 103, 112005 (2021), arXiv:2103.09969.
  * (14) R. Aaij et al. [LHCb collaboration], JHEP 06, 019 (2021), arXiv:2103.11058.
  * (15) R. Aaij et al. [LHCb collaboration], Phys. Lett. B 771, 21-30 (2017), arXiv:1701.01871.
  * (16) R. Aaij et al. [LHCb collaboration], Phys. Rev. Lett. 122, no.19, 191803 (2019), arXiv:1903.01150.
  * (17) M. Pivk and F. R. Le Diberder, Nucl. Instrum. Meth. A 555, 356-369 (2005), arXiv:physics/0402083.
  * (18) R. Aaij et al. [LHCb collaboration], arXiv:2204.12228.
  * (19) R. Aaij et al. [LHCb collaboration], arXiv:1808.08865.


# Reconsidering utility: unveiling the limitations of synthetic mobility data
generation algorithms in real-life scenarios

Alexandra Kapp<EMAIL_ADDRESS>0000-0002-8348-8958 Hochschule
für Technik und Wirtschaft Berlin, University of Applied
SciencesBerlin12459Germany and  Helena Mihaljević  helena.mihaljevic@htw-
berlin.de 0000-0003-0782-5382 Hochschule für Technik und Wirtschaft Berlin,
University of Applied SciencesWilhelminenhofstraße 75ABerlin12459Germany

(2023; 20 February 2007; 12 March 2009; 5 June 2009)

###### Abstract.

In recent years, there has been a surge in the development of models for the
generation of synthetic mobility data. These models aim to facilitate the
sharing of data while safeguarding privacy, all while ensuring high utility
and flexibility regarding potential applications. However, current utility
evaluation methods fail to fully account for real-life requirements.

We evaluate the utility of five state-of-the-art synthesis approaches, each
with and without the incorporation of differential privacy (DP) guarantees, in
terms of real-world applicability. Specifically, we focus on so-called trip
data that encode fine granular urban movements such as GPS-tracked taxi rides.
Such data prove particularly valuable for downstream tasks at the road network
level. Thus, our initial step involves appropriately map matching the
synthetic data and subsequently comparing the resulting trips with those
generated by the routing algorithm implemented in OpenStreetMap, which serves
as an efficient and privacy-friendly baseline.

Out of the five evaluated models, one fails to produce data within reasonable
computation time and another generates too many jumps to meet the requirements
for map matching. The remaining three models succeed to a certain degree in
maintaining spatial distribution, one even with DP guarantees. However, all
models struggle to produce meaningful sequences of geo-locations with
reasonable trip lengths and to model traffic flow at intersections accurately.
It is important to note that trip data encompasses various relevant
characteristics beyond spatial distribution, such as temporal information, all
of which are discarded by these models. Consequently, our results imply that
current synthesis models fall short in their promise of high utility and
flexibility.

privacy, location privacy, synthetic data generation, generative models,
mobility data, trajectory data

††journalyear: 2023††copyright: rightsretained††conference: The 31st ACM
International Conference on Advances in Geographic Information Systems;
November 13–16, 2023; Hamburg, Germany††booktitle: The 31st ACM International
Conference on Advances in Geographic Information Systems (SIGSPATIAL ’23),
November 13–16, 2023, Hamburg, Germany††doi: 10.1145/3589132.3625661††isbn:
979-8-4007-0168-9/23/11††ccs: Security and privacy Usability in security and
privacy††ccs: Applied computing Transportation††ccs: Security and privacy Data
anonymization and sanitization

##  1\. Introduction

The field of synthetic mobility data generation has experienced rapid growth,
primarily fueled by privacy concerns that hinder the release of sensitive
personal movement data. In essence, respective algorithms learn statistical
distributions from raw data and employ them to generate synthetic data that
emulate a similar distribution, while (supposedly) safeguarding sensitive
personal information. Within the domain of mobility data, a variety of
algorithmic approaches exist that can be categorized in terms of the specific
type of mobility they aim to model. A frequently considered type of mobility
in respective literature refers to ‘trips’ which consist of fine granular
routes connecting an origin and a destination, such as taxi rides or GPS-
tracked bicycle tours. This paper is focused on such trips, in contrast to
mobility data that entails per person a sequence of stay locations over the
course of a longer period of time, such as check-ins at restaurants or other
points of interest.

One primary objective of trip data generation algorithms is to produce
‘plausible’ trips. Respective evaluations typically involve comparing
aggregate statistics between raw and synthetic data, such as spatial
distributions where space is commonly discretized based on a grid of a
selected resolution. This operationalization often falls short in meeting
real-life requirements: depending on the underlying (coarse) grid, the
resulting synthetic trips usually do not follow the road network and instead
jump over buildings and rivers in an unrealistic manner (Sun et al., 2023).

However, the benefit of trip data, unlike other types of mobility data, is its
fine granularity such that it can be mapped to a road network. This especially
enables analyses such as calculating average speeds or traffic volumes per
road segment, which are valuable for applications like routing and urban
planning. Furthermore, accurate representation of traffic flow at
intersections facilitates optimized traffic light management (Wei et al.,
2020). Bicycle trips, collected by smartphone apps like SimRa (Karakaya et
al., 2020), enable the identification of road traffic hazard zones.

Therefore, we evaluate state-of-the-art synthesis algorithms by initially
matching their generated trips to the road network. Subsequently, we compare
the matched trips with those generated by the routing engine in OpenStreetMap
which is a simple, efficient, and privacy-sensitive way to produce road-level
movement data based on origin-destination (OD) pairs. We argue that synthetic
data generation algorithms need to provide a higher utility than common
routing engines to justifiably provide added value.

In summary, we address the following research questions:

  * •

(RQ1) What constitutes high utility of trip data and how can it be measured?

  * •

(RQ2) What level of utility do state-of-the-art synthesis models reach on
these measures in comparison to a routing baseline?

  * •

(RQ3) Can a satisfactory utility level still be provided given (differential)
privacy guarantees?

The remainder of this paper is structured as follows: We commence by
presenting an overview of the five evaluated state-of-the-art synthesis
algorithms. In Section 3, we address RQ1 and propose a formulation of utility
for trip data and suitable approaches for its measurement. Section 4 focuses
on the experimental setup, while the results are presented in Section 5.
Finally, we conclude by discussing our findings and possible future research.

##  2\. Synthesis Algorithms

In recent years, a series of models for generating synthetic mobility data
have emerged, aiming to facilitate the sharing of fine-granular datasets in a
privacy-preserving manner. These algorithms learn statistical distributions
from a raw dataset and generate a synthetic counterpart based on the learned
distributions. Nonetheless, without additional privacy measures, there is no
guarantee that the synthesis algorithm does not inadvertently reproduce real
trips or reveal sensitive information through the preserved statistical
distributions (Luca et al., 2021). To address this concern, many models
incorporate additional privacy mechanisms, often in the form of Differential
Privacy (DP) guarantees.

DP provides mathematical guarantees for preserving individual privacy (Dwork,
2006). The core idea behind DP is that the output of an algorithm remains
largely unaffected if the records of a single individual are either removed or
added. This mechanism effectively limits the influence of a single individual
on the overall analysis outcome, thus preventing the reconstruction of their
specific data. Generally, a typical approach to achieving DP in numeric
functions consists of adding calibrated noise drawn from a Laplace
distribution to the function’s output. In the context of synthesis algorithms,
noise is commonly added to the underlying distributions such as that of
origins or OD pairs before synthetic samples are generated.

Amongst the published synthesis algorithms, we have carefully chosen five
models for our evaluation to ensure a diverse representation of modeling
techniques. Our selection process took into consideration various factors,
especially the clarity of reasoning behind their approaches, promising results
demonstrated in respective evaluations, and the availability of source code,
either as open source or obtainable upon request. The selection process
resulted in the following models: AdaTrace(Gursoy et al., 2018),
PrivTrace(Wang et al., 2023), BiLSTM(Blanco-Justicia et al., 2022), DP-
Loc(Lestyán et al., 2022), and TrajGAIL(Choi et al., 2021).

AdaTrace (Gursoy et al., 2018) is a frequently cited and benchmarked
differentially private model. Coordinates are discretized using an $NxN$ grid
of uniform cells. Synthetic trips are generated in three steps: First, OD
pairs are sampled from a differentially private OD distribution. Second, the
number of points per sequence is sampled from a differentially private
distribution of the respective OD pair. Third, a sequence between a start and
an endpoint is constructed by repeatedly sampling the next location until the
sequence length is reached. The next-location sampling is based on a Markov
model which holds DP transition probabilities for each location, i.e., grid
cell, to each other location, given the previous location and the destination.
The exact coordinates of the synthetic locations are sampled uniformly at
random from within the grid cell.

To ensure a more accurate spatial distribution while maintaining a high level
of privacy, the authors make use of a ‘density-aware grid’. When a grid cell
contains a small number of records, it is retained at a coarse top-level
resolution. On the other hand, when the number of records in a grid cell is
large, it is split into a finer-grained resolution. Note that the Markov model
relies on the coarse top-level grid, with the density-aware grid coming into
play only during the final step of sampling coordinates. This comes with some
implications for the resulting synthetic data: Despite using a coarse top-
level grid, the aggregate spatial distribution is well maintained due to the
preservation of hotspots through the density-aware grid (see Appendix B of
(Gursoy et al., 2018)). However, it is worth noting that the distance between
two consecutive points in the generated data is determined by the resolution
of the coarse top-level grid. The compatibility with DP is an essential aspect
of the model’s architecture, and therefore, the implementation does not
foresee the possibility of training the model without DP.

The recently proposed model PrivTrace (Wang et al., 2023) aims to improve upon
AdaTrace, which supposedly lacks sufficient transition information due to its
first-order Markov chain model. Additionally, it addresses the limitations of
DPT (He et al., 2015), where the high-order Markov chain model introduces
excessive noise due to the incorporation of DP. PrivTrace follows a similar
approach as AdaTrace but with some notable distinctions. In PrivTrace,
synthetic sequences are generated using a first-order and a second-order
Markov chain. Sequence sampling is stopped based on ‘virtual ends’ in the
Markov model instead of a sampled sequence length and a drawn destination.
Additionally, PrivTrace incorporates transition probabilities of more fine-
granular grid cells into the Markov Model, claiming to thereby provide better
transition information. Thus, unlike AdaTrace, the distance between
consecutive points is not determined by the top-level grid resolution. Again,
this model always provides DP guarantees.

Lestyán et al. (Lestyán et al., 2022) propose DP-Loc, a differentially private
model that initially performs a dimensionality reduction by only considering
cells that have been visited more often than a certain threshold. Then,
similar to AdaTrace, DP-Loc first generates OD pairs and then constructs a
trip based on transition probabilities. For the OD generation, a variational
autoencoder is used, while transition probabilities are captured using a
feedforward neural network (FNN). The authors argue that the basic FNN is
adequate, as the information of the current location alone is sufficient to
predict the next location, unlike, for example, models that specifically aim
to model sequences. To guarantee DP, Gaussian noise is added to the
distribution of visit counts per cell (Dwork and Roth, 2014), and both neural
networks are trained using Differentially Private Stochastic Gradient Descent
(DP-SGD) (Abadi et al., 2016), which adds noise to clipped gradients during
training. Notably, unlike the two other models, DP-Loc includes the generation
of start times of trips.

Blanco-Justicia et al. (Blanco-Justicia et al., 2022) propose the utilization
of a BiLSTM, a bidirectional long short-term memory network, a recurrent
architecture that has proven superior performance in modeling sequences such
as time series or natural language. Considering a visited location as a word
and a trip as a sentence, the principles of autoregressive text generation
using RNNs can be adopted to generate trips. For the task of trip generation,
a start location is selected at random. Using the BiLSTM, the location is
extended in an autoregressive manner to generate subsequent locations until
the sequence length sampled from the respective distribution is reached. The
authors propose a privacy mechanism that samples one of the top three next-
location predictions uniformly at random from the probability distribution of
the next locations. This approach comes with a few downsides. Firstly, privacy
is not formally guaranteed. Second, utility is not well maintained, as the
results in the original paper indicate major jumps between consecutive points.
We thus follow the authors’ advice for future work and apply a DP mechanism to
the model using DP-SGD, more specifically, the Tensorflow implementation of a
DP Adam optimizer.

TrajGAIL (Choi et al., 2021) is based on inverse reinforcement learning that
makes use of the representation of an agent that moves around according to a
set of actions and a learned policy. The original paper considers a
chessboard-like road network, for which only the actions ‘forward’, ‘left’,
and ‘right’ are included. Generally, the set of actions needs to be specified
and for each intersection, all options need to be defined. In chapter 4.1 we
elaborate on our adaptions to allow for more heterogeneous road networks. The
model does not provide any privacy guarantees or mechanisms. However, we still
include the model in our evaluation to elaborate on its suitability and the
potential for further DP advancements.

##  3\. Utility measurement

Defining and evaluating the utility of synthetic mobility data is a complex
task. Unlike some other domains such as medical data, where typical
applications like diagnosis prediction can be framed as classification tasks,
typical mobility data applications do not lend themselves easily to such
formulations. As a result, utility is often assessed based on the degree of
statistical similarity between the synthetic and raw data for different
mobility characteristics. A mobility characteristic, like the spatial
distribution, is operationalized by concrete measures, like the Jensen-Shannon
divergence (JSD) of visits per grid cell. Accordingly, hitherto executed
evaluations of the considered synthesis models are based on similarity
measures concerned with all or some of the following characteristics: spatial
distribution, OD pairs, frequent patterns of sequences, and trip lengths.
However, the measured level of utility is highly dependent on the selected
characteristics and their operationalization. For example, a high similarity
of the spatial distribution does not necessarily ensure that the generated
trips consist of reasonable OD combinations. Furthermore, achieving high
similarity based on, e.g., the JSD given a coarse grid with large cells (e.g.,
$2km$ x $2km$) provides only limited insight into the preservation of spatial
distribution at a more detailed level.

Moreover, assessing utility based solely on these measures may not provide a
comprehensive understanding of how well the synthetic data performs in real-
life scenarios, like the examples given in the introduction. To overcome this
limitation, we propose adopting a practitioner’s perspective to specifying
high utility for synthetic trip data and identifying appropriate measurements.
By doing so, we aim to capture the utility of synthetic data more effectively
in real-world applications.

Mobility data often encompasses more than just geo-locations, including
temporal information, mobility modes, and user demographics. These additional
aspects contribute to a broader range of characteristics that practitioners
may find essential (Kapp, 2022). However, none of the five evaluated models
considers user-related information, and only one model generates timestamps.
Consequently, only characteristics addressing solely geo-locations can be
meaningfully evaluated, reducing the set of characteristics to the
distribution of OD counts, trip lengths, and the spatial distribution of
records.

Since the distribution of OD counts does not depend on the specifics of trip
data, we decided to exclude respective evaluations and focus on trip lengths
and spatial distributions, as they rather allow to capture the inherent
complexity of fine-granular sequences resembling street-level movements.

#### Map matching

Tasks based on trip data are commonly based on a street-level granularity,
such as assessing traffic volumes on roads or occupancy information of public
transit lines.However, all models under evaluation are based on grids that do
not consider road networks and thus produce implausible trips that, e.g.,
cross buildings or rivers. Thus, we introduce an additional processing step of
map matching such that all synthetic trips are ‘snapped’ onto the closest
road, and consecutive records are connected according to the laws of physics
and road regulations. We refer to data as produced by the model as original
and its matched variation as matched. In Section 5.1, we evaluate the
suitability of considered synthetic datasets for map matching.

#### Routing as baseline

Furthermore, for the respective comparisons, we introduce routing as a
baseline. Routing engines such as Google Maps, the Open Source Routing Machine
(OSRM), or OpenTripPlanner use road and public transit network data to
generate routes, typically optimized for the shortest or fastest paths. Thus,
these engines offer an efficient and privacy-preserving approach to create
realistic routes between a start and an endpoint. However, it’s important to
note that routing does not reflect real-life route choices comprehensively, as
it cannot consider all factors relevant to individuals. For example, a cyclist
might prefer a route through a park, even if it takes a bit longer, in order
to avoid cobblestone streets or streets with too much car traffic. This
highlights the value of actual user data for the work of practitioners (Lu et
al., 2018; Broach et al., 2012; Prato, 2009). We argue, that synthetic data
generation algorithms need to outperform routing engines to provide
justifiable additional value. A routed variation of a dataset is created by
routing the identical start and destination location of each included trip.

#### Trip lengths

Existing assessments of trip lengths generally indicate that generated
synthetic data reaches a satisfactory level of similarity to the raw data.
However, these evaluations only consider implausible unmatched trips, thus the
trip length says little about the actual traveled distance if one were to
follow the route. We argue that utility concerning trip length can only be
considered high when taking into account the trip length of the route matched
to the road network. To identify synthetic trips that are implausible due to
unreasonable loops and unnecessary winding paths, we suggest conducting a
secondary evaluation of trip length which is based on comparing the synthetic
trips to the straight-line (SL) distance between their origin and destination.

#### Spatial distribution

To capture the spatial distribution of trips on a street level, a sufficiently
fine-grained grid is required for evaluations. As a rough guideline, we
consider grid cells with dimensions of $1km$ x $1km$ to capture a neighborhood
and cells of $40m$ x $40m$ provide details on the level of roads. As a proxy
for traffic volumes per road segment, we suggest evaluating the spatially
aggregated trips based on a grid with a resolution on street level (of $40m$)
by computing the Jensen-Shannon-divergence (JSD) between the matched raw
dataset and the variants of synthetic datasets, where each cell is considered
as a ‘segment’.

It is difficult to interpret the values of the JSD in terms of practical
utility. We thus additionally propose the downstream task of identifying
avoided and preferred roads. For each trip, the matched and routed versions
are compared; see Fig. 1 for a visual example. Each road segment $s$ that is
traversed by the matched but not the routed trip is considered ‘preferred’ and
the counter $\mathrm{npref}_{s}$ is increased by 1. Conversely, each segment
that is traversed by the routed but not the matched trip is considered
‘avoided’ and its counter $\mathrm{navoid}_{s}$ is increased by 1. We define
the preference score of $s$ as

$\mathrm{preferenceScore}_{s}=\frac{\mathrm{npref}_{s}-\mathrm{navoid}_{s}}{n_{s}},$

where $n_{s}$ equals the total number of times that $s$ has been passed by a
matched or a routed trip.

Preference scores can be assessed statistically, e.g., using the Pearson
correlation coefficient between scores from raw and synthetic data. Secondly,
the correct classification (preferred ¿ 0, avoided ¡ 0, neither = 0) can be
analyzed in terms of standard classification metrics such as accuracy and
F1-scores. To approach the downstream task from a practical perspective, we
suggest a measurement of human inference, such as a survey. See Section 4.4
for our realization.

Figure 1. Schematic illustration: preferred segments (green cells) are
traversed by the matched trip (green line), but not its routed counterpart
(purple line), and vice versa, they are considered avoided (purple cells).

Finally, we propose to assess the spatial distribution with respect to traffic
flow at intersections which is another relevant application (Li et al., 2010)
for example for traffic signal management (Wei et al., 2020). In this context,
we refer to traffic flow as the entirety of movement patterns at an
intersection. A movement pattern is described by the arrival road segment, the
turning behavior, and the destination road segment. Similar patterns are
grouped into movement clusters. As trips are already matched to the road
network, movement patterns can easily be aggregated by clustering trips
spatially based on a suitable distance metric. We refer to Section 4.5 for our
utilized implementation.

In summary, we propose to measure the utility of trip data by comparing
synthetic data, after it has been matched with the road network, to its routed
counterpart with respect to the following aspects: (1a) distribution of trip
lengths, (1b) distribution of trip lengths in relation to the OD straight-line
distance, (2) distribution of traffic volumes on road segments, (3)
identification of avoided and preferred roads, and (4) traffic flow at large
intersections.

##  4\. Experimental setup

###  4.1. Raw dataset

For our evaluation, we use the openly available SimRa dataset (Bermbach, 2021;
Bermbach and Karakaya, 2021; Karakaya and Bermbach, 2022). SimRa (Karakaya and
Bermbach, 2022) is a smartphone app for cyclists that records GPS traces,
sampled every few seconds, to track near-miss incidents. We use the trips
collected in the central area of Berlin limited to records within longitudes
of 13.267 and 13.482, and latitudes between 52.445 and 52.576, thus covering
about 14x14 $km^{2}$. The dataset comprises 28,345 trips between 2019 and
2022. Near-miss incident information is discarded for our evaluation.

###  4.2. Configurations for synthesis models

For each evaluated synthesis algorithm, including both the differentially
private (DP) and non-DP variants, when applicable, we generate a synthetic
dataset containing 5,000 trips. To account for the non-deterministic nature of
model-based data generation, we repeat this procedure five times and average
the results. A privacy budget of $\varepsilon=2$ is used for the DP condition,
which is the highest privacy budget setting in the evaluations of AdaTrace and
PrivTrace. As the implementations of AdaTrace and PrivTrace do not provide a
non-DP option, we set a very large privacy budget of $\varepsilon=1,000,000$
for the base condition ‘without DP’. Datasets are generated on a machine
equipped with an Nvidia A30 GPU, an Intel(R) Xeon(R) Gold 6346 CPU, and 251 GB
RAM.

The choice of spatial granularity is pivotal to our utility formulation. Thus,
we employ at the very least the finest granularity proposed by the respective
authors. When computationally feasible, we opt for even finer resolutions. It
is noteworthy that AdaTrace uses an adaptive grid, adjusting the spatial
granularity based on the density within each grid cell. However, as explained
in Section 2, the distance between consecutive points is determined by the
top-level grid, which defaults to 6 x 6 cells in the respective source code.
For the utilized SimRa dataset this would result in a top-level cell size of
$2.5km$ x $2.5km$ and an average sequence length of 3.6 points. Such distances
between consecutive points would not meet the requirements with respect to our
utility measurement, as stated in Section 3. We thus adjust the top-level grid
to $N=28$ which corresponds to a cell size of $500m$ x $500m$. A finer-grained
grid with a cell size of $250m$ x $250m$ exceeds the available memory.

The spatial granularity of the top-level grid of PrivTrace is determined by a
parameter $K$. We use a resolution of $500m$ ($K=28$) for the sake of
computational feasibility. Using a finer grid with a resolution of $250m$
significantly increases the runtime from 15 minutes to 34.5 hours. We further
adjust AdaTrace and PrivTrace to generate coordinates with a precision of four
decimals, as both round to only two decimals, which would correspond to a
granularity of $\sim 1km$.

The BiLSTM uses a similar neural network architecture as (Blanco-Justicia et
al., 2022). To speed up training and prevent overfitting, we implement an
early stopping criterion causing the training to stop if the validation loss
increases or stagnates for more than one epoch. Also, to enhance utility, we
draw start locations from the distribution of start locations in the raw data
instead of relying on random sampling. We use a grid resolution of $250m$,
which is roughly equivalent to the authors’ fine-granular choice.
Additionally, we tested a finer resolution of $100m$, however, we discarded it
due to computational infeasibility as it takes 8 hours for training and about
25 hours for trip generation, compared to 75 minutes for training, and 8 hours
for generating when a resolution of $250m$ is employed. Like the authors, we
modify the final dense layer based on the 3,188 cells that have been visited
at least once. We also conduct a preprocessing step where all trips above a
given trip length are discarded to save training resources and set the maximum
length to 50 steps. In our setup, we yield an early stopping after 16 epochs,
a training loss (accuracy) of 0.44 (86.67%), and a validation loss (accuracy)
of 0.54 (85.68%).

To ensure DP, we apply the Laplace mechanism to the distribution of start
locations and trip sequence lengths, respectively. As a fine-granular grid is
expected to decrease utility in a DP setup due to a higher level of required
noise, we initially test the DP variation with a coarser resolution of $500m$.
The BiLSTM final dense layer is accordingly adjusted to 900 cells. The BiLSTM
utilizes the DP Adam optimizer with an L2 clipping norm of 1, a noise
multiplier of 1.4, and 64 micro-batches. The privacy budget is split such that
$\varepsilon=1$ is allocated for the BiLSTM and $\varepsilon=0.5$ for each
distribution. The batch size is reduced to 128 (due to memory limits), and 20
epochs are trained without early stopping. It takes 46 hours of training, thus
a multitude of the non-DP version, yielding a training loss (accuracy) of 5.59
(10.56%) and a validation loss (accuracy) of 5.41 (12.82%). Due to unusable
results for map matching, as we will show in the following Section 5.1, we
refrain from evaluations with a finer grid resolution.

We run DP-Loc with a $500m$ grid resolution.As the output produces multiple
datasets for different iterations of a Metropolis-Hastings algorithm, we
follow the authors’ advice for smaller datasets and use 100 iterations. Again,
due to results unsuitable for map matching (see Section 5.1) we do not test
further resolutions.

To employ TrajGAIL without translating the Berlin road network to the TrajGAIL
network notation, we define the network based on a grid. For each cell, its
eight neighboring cells are considered to be within reach according to one of
eight respective actions. We project the dataset to a grid with a $500m$
resolution which results in a significantly larger network compared to the
dataset evaluated by the authors of TrajGAIL, which only encompasses 9
intersections, and thus substantially higher computation times. While one
iteration for their dataset only takes 8 seconds, the processing time for the
SimRa dataset extends to approximately 3.5 minutes. Consequently, running
20,000 iterations, similar to the authors’ evaluation, would require over 48
days to complete. Due to this computational infeasibility, TrajGAIL is
excluded from further evaluations.

###  4.3. Matching and routing implementation

We use the OpenStreetMap Routing Machine (OSRM) (Luxen and Vetter, 2011) match
service (API) to snap trips onto the OpenStreetMap road network. The parameter
$radius$ of the API is intended to set the GPS precision. We chose a setting
of 10 meters for the raw and 20 meters for synthetic datasets which proved to
be a reasonable setting within acceptable computation time.111Note that map
matching is computationally expensive; usage in practice would require
optimization such as parallelization to be feasible. To set up OSRM, we used
the OpenStreetMap data excerpt for Berlin, provided as $PBF$ file by
Geofabrik222https://www.geofabrik.de/data/download.html, from 17th November
2022 using the bicycle traffic mode. There are cases in which OSRM map
matching does not produce entirely accurate results; see Appendix 6.1 for
potential issues and respective validation analyses. For the routing baseline,
we use the OSRM Route Service based on a similar OSRM setup. See Figure 2 for
an example of created trip variations.

Basemap: OpenStreetMap contributors

originalmatchedroutedstraight-line

Figure 2. Example for raw (left) and AdaTrace (right) trip in four variations.

###  4.4. Road preference survey

We evaluate the downstream task of road preference detection with a survey on
40 selected meaningful examples of roads. Participants are asked to decide for
each road, whether they consider it to be ‘avoided’, ‘preferred’, or ‘not
recognizable’, based on the displayed preference score. To select roads, we
initially filter segments that have clearly either been preferred or avoided
by restricting to those with a preference score $>0.5$ or $<-0.5$. Next, we
limit the selection to the top 10% of visited and routed segments to focus on
highly frequented areas. Finally, to obtain coherent clusters representing
entire roads that are either avoided or preferred, adjacent remaining segments
of the same class are merged. 20 avoided and 20 preferred roads are selected
from the largest clusters. The survey consists of map cutouts displaying
preference scores alongside selected roads (see Figure 3). To enhance clarity,
only preference scores from the top 25% of frequented segments are shown which
are more likely to be robust and representative. The survey is conducted
online, in German, and for each condition, at least 10 people are recruited.
Each questionnaire contains only one condition to prevent learning effects.

Figure 3. Examples of survey questions. The preference score is overlaid on a
map cutout alongside selected roads. Answers are given via radio buttons for
each road.

###  4.5. Traffic flow evaluation

We evaluate traffic flow preservation based on ten major intersections. They
are selected by initially filtering the top 15 most visited cells from the raw
data based on a grid with $500m$ resolution and manually setting ten
meaningful bounding boxes within them. For each intersection and each routed
and matched dataset, trips are cut according to the respective bounding box.
The pairwise distance between these trips is computed with the Hausdorff
distance (HD). Complete-linkage agglomerative hierarchical clustering is
employed based on the resulting distance matrix. To determine movement
clusters, the hierarchical tree is cut at a height of 5 meters 333In
experiments using various cutoff values, the relatively strict value of 5
proved to be the most suitable, as it effectively prevents false positives
while minimizing false negatives (since trips are matched to the same road
network, resulting in minimal variance).

To assess the preservation of movement patterns by synthesis algorithms, the
clusters of each synthetic dataset are linked with the clusters of the raw
data. To link clusters, we employ a simple greedy matching algorithm that
iterates over all clusters in the raw data. For each raw data cluster, we find
the synthetic data cluster with the smallest HD. If the distance is smaller or
equal to 5, they are considered a match, otherwise, the raw data cluster
remains unmatched. To ensure computational feasibility, not all trips, but
randomly selected representatives from each cluster of both datasets are used
for distance computation. Finally, we compare the counts for each movement
pattern using the normalized discounted cumulative gain (nDCG) which is a
common measure to assess ranking quality in information retrieval. Only the
$k$ highest ranked scores are considered. The normalized version has a range
from 0 to 1, where a score of 1 signifies perfect retrieval.

##  5\. Results

###  5.1. Matching ability

The longer the distance between consecutive points the less suitable is the
application of map matching; in the extreme case where a trip would only
include origin and destination points, map matching would be equal to routing.
Thus, for synthetic data to be usable for map matching we require the distance
between consecutive points for the majority of trips to be within the
magnitude of the spatial resolution used for data generation.444Note, that the
raw data also includes outliers of jumps up to $10km$ where some are due to
faulty GPS sensor signals and others because a trip leaves and re-enters the
defined bounding box at a different location. Table 1 shows the distribution
of distances between two consecutive points for each synthetic dataset
(excluding repetition of identical locations).

Table 1. Distribution of distances between two consecutive points (excluding repetition of identical locations) in meters. | min | 25% | median | 75% | max
---|---|---|---|---|---
raw | 1 | 11 | 16 | 20 | 10,197
AdaTrace | 7 | 441 | 589 | 746 | 1,643
AdaTrace DP | 7 | 501 | 664 | 835 | 2,008
PrivTrace | 2 | 374 | 526 | 677 | 1,135
PrivTrace DP | 15 | 329 | 486 | 649 | 1,109
BiLSTM | 248 | 249 | 250 | 250 | 18,513
BiLSTM DP | 498 | 2,999 | 5,226 | 8,044 | 17,338
DP-Loc | 498 | 999 | 1,412 | 2,554 | 13,436
Dp-Loc DP | 498 | 999 | 1,500 | 4,607 | 14,304

While AdaTrace (DP), PrivTrace (DP), and BiLSTM yield distances in the
required order of magnitude, DP-Loc proves not suitable for map matching with
a median distance of $1.4km$ ($1.5km$ for the DP version). An examination of
the trips generated by DP-Loc revealed that after only a few initial points a
large jump to the destination followed. As our evaluation is based on road
network matching, we discard DP-Loc from further analyses as well as the DP
version of BiLSTM, which only consists of random jumps with a median distance
of $5km$. This yields the following final set of synthetic datasets for the
evaluation: AdaTrace, AdaTrace DP, PrivTrace, PrivTrace DP, and BiLSTM.

See Appendix 6.2 for visualizations of spatial distributions and example trips
of each original dataset (without DP) and Appendix 6.3 for spatial
distributions of matched and routed variations.

###  5.2. Trip lengths

As shown in Table 2, all synthetic median SL distances tend to be shorter than
the raw data’s SL distance of $4.57km$. AdaTrace is most similar and within a
reasonable distance, followed by BiLSTM, while the other three synthetic data
are too far off. More precisely, PrivTrace is much shorter with a median
distance of $1km$ and even only $470m$ for its DP version, while the SL
distance of AdaTrace DP is a lot longer than that of the raw data. In contrast
to the described tendency for SL distances, the original trips of AdaTrace and
BiLSTM tend to be longer than the original raw trips. Interestingly, despite
AdaTrace DP having the furthest deviation in terms of absolute value, its SL
ratio is closest to that of the raw data. While PrivTrace (DP) remains
significantly below the respective value of the original data, the increase
compared to the straight line is the highest with a median of 216% (184%) of
the SL distance. These observations suggest that synthetic data is more
circuitous than real-life trips. This effect is even more evident in the
matched datasets, as the SL ratio increases even more across all models.

Table 2. Median of trip lengths in $km$ for each dataset and their variations. In brackets: median ratio of respective trip length to its straight-line (SL) distance counterpart. | SL | original | matched | routed
---|---|---|---|---
raw | 4.57 | 5.79 | (120%) | 5.47 | (130%) | 5.63 | (120%)
AdaTr. | 4.10 | 7.45 | (170%) | 9.01 | (212%) | 5.12 | (120%)
Ada. DP | 6.84 | 8.43 | (120%) | 9.71 | (150%) | 8.47 | (120%)
PrivTr. | 1.02 | 2.55 | (216%) | 3.15 | (268%) | 1.42 | (130%)
Priv. DP | 0.47 | 1.05 | (184%) | 1.28 | (229%) | 0.73 | (140%)
BiLSTM | 3.75 | 7.31 | (162%) | 7.89 | (200%) | 4.65 | (120%)

As expected, the routing algorithm reliably produces trips with a median ratio
to the SL distance of 120%-140% for all models. In comparison to the matched
synthetic trips, the routed lengths are thus much closer to those of the raw
trips and, for AdaTrace (DP) and BiLSTM, also with regards to the absolute
value. Thus, none of the models succeeds at producing plausible trip lengths.

###  5.3. Traffic volume

Table 3 shows the JSD between matched raw data and all dataset variations,
based on aggregations on a grid with a $40m$ resolution555Note that we do not
only account for cells that contain a record but also those that are passed by
the line from one record to the consecutive.. The JSD of the synthetic data SL
versions are all in the same order of magnitude as the JSD of the raw SL
version, providing a baseline upper bound of the JSD for each synthetic
dataset. (Recall that the higher the value the lower the similarity of the
respective datasets.) The spatial distribution of AdaTrace and PrivTrace
original datasets, with and without DP, improve compared to the straight-line
distribution, though only marginally. The JSD for the original BiLSTM dataset
even increases.

Table 3. JSD values for traffic volumes between each dataset variant and the baseline of matched raw data. Bold font indicates the best variation.  | SL | original | matched | routed
---|---|---|---|---
raw | 0.60 | 0.15 | 0.00 | 0.39
AdaTrace | 0.60 | 0.58 | 0.39 | 0.40
AdaTrace DP | 0.61 | 0.60 | 0.43 | 0.46
PrivTrace | 0.63 | 0.59 | 0.43 | 0.45
PrivTrace DP | 0.69 | 0.67 | 0.58 | 0.60
BiLSTM | 0.59 | 0.62 | 0.44 | 0.40

All JSD values for the matched versions show the expected decrease, supporting
our claim that map matching is needed for usable results on a street level.
For AdaTrace and PrivTrace the results outperform their routed counterpart, at
least slightly. On the contrary, the routed version of BiLSTM outperforms its
matched one. The better performance of AdaTrace and PrivTrace comes likely due
to their adaptive grid which captures ‘hotspots’ on a more fine granular level
than the top-level grid. The low performance of the BiLSTM model is presumably
rooted in the static grid utilized for training and data generation, and the
difference between the grid resolution chosen in training ($250m$) vs.
evaluation ($40m$) that reflect street-level relations. Experiments show that
a JSD based on a coarser grid using a $250m$ resolution yields a superior
value also for the matched BiLSTM data in comparison to the routed version.
Thus, the BiLSTM might only obtain superior results for its matched data on a
street level if a more fine-granular resolution is used for data generation.
It is thus interesting to note that the map matching is not sufficient to
compensate for the coarse resolution used for data generation.

AdaTrace shows the best overall results. It yields the only competitive JSD
with its matched version to the routed raw version. Also, the JSD values of
AdaTrace DP are only slightly worse than AdaTrace without DP. Unlike
PrivTrace, which shows a majorly decreased performance for its DP version.

###  5.4. Road preference

####  5.4.1. Statistical similarity

We assess the preservation of road preference in synthetic data by comparing
their preference scores with the ground truth obtained from the raw data. We
test variations of two hyperparameters for the classification task. (1) Rarely
visited segments are discarded based on a frequency threshold. Different
thresholds are evaluated: top-100%, top-75%, and top-25% of frequented
segments, based on the series of all $n_{s}$, are considered. Note that a
threshold of top-100% frequented segments means that all segments with at
least 1 record are included. (2) To account for cases where values are close
but do not fall into the same class (e.g., the preference score for a segment
is 0.1 according to the raw and -0.1 according to the synthetic dataset), we
set a tolerance level such that two values are considered correctly classified
if they do not differ more than the tolerance level. We consider values of 0
and 0.3. As shown in Table 4, the BiLSTM clearly outperforms AdaTrace and
PrivTrace on all settings with respect to the correlation coefficient, the
accuracy, and the F1-score of the class ‘avoided’, while it is outperformed in
terms of the F1-score of the ‘preferred’ class in three out of four
hyperparameter settings though with less pronounced differences. As expected,
setting a tolerance level increases the scores, as classes are assigned more
generously. Further, intuitively almost all scores increase with an increasing
frequency threshold, as highly frequented cells are expected to be captured
with higher accuracy by the models.

Table 4. Preference score evaluation for different frequency thresholds (as top-$x$% frequented segments) and tolerance levels based on Pearson correlation coefficient $r$, accuracy and F1-score, precision, and recall for the classes ‘avoided’ and ‘preferred’. For each hyperparameter setting, i.e., each $n$-th row per block, the best value is depicted in bold font. |  frequ. thres. |  tol. lev. |  $r$ |  accu. (%) |  avoided F1 [prec., rec.] |  preferred F1 [prec., rec.]
---|---|---|---|---|---|---
Ada |  100 |  .0 |  .40 |  56 |  .46 [.64, .36] |  .70 [.58, .89]
Trace |  75 |  .0 |  .46 |  58 |  .48 [.69, .37] |  .72 [.60, .90]
|  |  .3 |  .46 |  63 |  .53 [.77, .41] |  .74 [.62, .92]
|  25 |  .3 |  .57 |  68 |  .64 [.82, .52] |  .75 [.65, .90]
Ada |  100 |  .0 |  .37 |  53 |  .51 [.54, .48] |  .65 [.55, .80]
Trace |  75 |  .0 |  .40 |  55 |  .53 [.57, .49] |  .67 [.58, .80]
DP |  |  .3 |  .40 |  60 |  .57 [.63, .52] |  .69 [.60, .83]
|  25 |  .3 |  .44 |  66 |  .70 [.70, .70] |  .66 [.65, .67]
Priv |  100 |  .0 |  .27 |  51 |  .28 [.51, .19] |  .67 [.55, .85]
Trace |  75 |  .0 |  .31 |  53 |  .29 [.54, .20] |  .68 [.56, .88]
|  |  .3 |  .31 |  57 |  .35 [.63, .24] |  .70 [.58, .90]
|  25 |  .3 |  .41 |  59 |  .36 [.83, .23] |  .71 [.57, .94]
Priv |  100 |  .0 |  .19 |  48 |  .33 [.43, .26] |  .64 [.59, .69]
Trace |  75 |  .0 |  .19 |  48 |  .33 [.43, .26] |  .64 [.59, .69]
DP |  |  .3 |  .19 |  55 |  .40 [.52, .33] |  .67 [.62, .73]
|  25 |  .3 |  .23 |  59 |  .43 [.62, .32] |  .70 [.60, .83]
Bi |  100 |  .0 |  .43 |  58 |  .59 [.59, .60] |  .67 [.63, .72]
LSTM |  75 |  .0 |  .48 |  61 |  .62 [.63, .62] |  .69 [.64, .76]
|  |  .3 |  .48 |  66 |  .66 [.67, .66] |  .72 [.67, .78]
|  25 |  .3 |  .59 |  72 |  .73 [.81, .66] |  .77 [.69, .87]

The class ‘preferred’ is detected best by all models. This is especially true
for AdaTrace (DP) and PrivTrace (DP) and can likely be explained with the
selection of coordinates in their generation algorithm: Recall that data
generation is based on discrete grid cells. While the BiLSTM always uses the
center of the grid cells to create coordinates, AdaTrace and PrivTrace sample
a random point from within the cell. This produces more variation and thus
more visited cells (see Appendix 6.3 for maps of respective spatial
distributions). Therefore, there is a bias towards ‘preferred’ classification:
AdaTrace (PrivTrace) classifies 79% (79%) of considered cells as preferred and
only 17% (13%) as avoided, while only 67% of cells are preferred in the raw
data and 36% avoided. Thus, the high ‘preferred’ F1-score is especially driven
by a high recall. In summary, the BiLSTM can be considered the best-performing
model in terms of road preference and avoidance.

Considering DP models for both AdaTrace and PrivTrace, there is only a slight
decrease in terms of accuracy, while the correlation coefficient decreases to
a larger extent. Interestingly, both PrivTrace DP and Adatrace DP detect
avoided roads slightly better than their non-DP counterparts. Further
investigation showed that this is a noise-induced artifact causing more
variation in OD pairs and thus a higher share of routed cells (24% for both,
AdaTrace and PrivTrace) which leads to an increased recall of ‘avoided’ and a
decrease for ‘preferred’, while the precision either decreases or remains the
same for all classes.

The outcomes do not indicate a perfect classification but suggest that models
have the potential to identify preferred and avoided roads to a certain
extent, particularly when focusing solely on heavily trafficked sections.

####  5.4.2. Survey

We assess the homogeneity of answers per condition with Krippendorff’s alpha
$\alpha_{K}$ (see Table 5) which is high for raw data and AdaTrace, while only
medium for all other datasets ($\alpha_{K}\geq 0.66$). However, these
discrepancies are seldom because participants directly contradict each other’s
assessments. Instead, they typically arise from certain participants adopting
a more conservative stance, opting for ‘not recognizable’ rather than making a
definitive choice between ‘avoided’ or ‘preferred’. In particular, the results
from the majority vote are robust when compared with sums of (in)correct
answers. Table 5 presents the percentage of accurately classified, incorrectly
classified, and unrecognizable roads among the 40 selected roads, based on the
majority vote of participants.

Table 5. Results of the road preference survey for 40 selected roads, presented as percentages of accurately classified roads in total and separated by class (preferred, avoided), the percentages of unrecognizable and incorrectly classified roads, and group homogeneity (Krippendorff’s $\alpha_{K}$). | $\alpha_{K}$ | accu. [pref., avoid.] | not recog. | incorrect
---|---|---|---|---
raw | 0.91 | 100 [100, 100] | 0 | 0
AdaTrace | 0.80 | 82 [90, 75] | 15 | 2
Ada. (DP) | 0.74 | 75 [80, 70] | 20 | 5
Priv. | 0.66 | 52 [70, 35] | 42 | 5
Priv. (DP) | 0.66 | 30 [45, 15] | 68 | 2
BiLSTM | 0.73 | 80 [75, 85] | 20 | 0

An accuracy of $100\%$ in raw routes supports our defined ground truth. Even
for all synthetic datasets, misclassification of roads was minimal, with most
discrepancies attributed to being classified as ’not recognizable’. This trend
was particularly noticeable in PrivTrace (DP). Generally, preferred roads are
more often classified correctly than avoided ones, except for BiLSTM. AdaTrace
demonstrates the highest performance, closely followed by BiLSTM. Even in its
DP version, 75% of the roads are still correctly classified. However, this
also suggests that about every fourth road is misclassified or not
recognizable. Considering that we only included the top 10% most frequented
cells for the selection of roads, these results presumably do not suffice in
practice.

Overall, the assessment of road preference indicates that especially AdaTrace
and BiLSTM demonstrate a certain level of success in preserving spatial
distribution information. We also find a set of inconclusive results with
regard to different analyses concerned with spatial distribution: With regards
to PrivTrace, even though its JSD slightly outperforms the BiLSTM’s, it
performs much worse in road preference classification. This is mainly driven
by a bad detection of avoided streets and likely due to implausible short-
distanced OD pairs, as seen in Section 5.2. Also, even though the BiLSTM
obtains a slightly better F1-score for preferred segments than AdaTrace (DP)
for the comparable hyperparameter setting of a top-25% frequency threshold,
the majority of individuals could identify 15 percentage points (5 percentage
points) more of preferred roads based on AdaTrace (DP) data than on BiLSTM
data.

###  5.5. Traffic flow at intersections

Figure 4 shows an example of an intersection displaying the top five traffic
movements for each dataset of their matched and routed version. In general,
for the synthetic data to offer added value, the nDCG of the matched version
should surpass that of the routed version. In Table 6, the averaged results
across all intersections are displayed. It can be observed that AdaTrace
performs better than its routing baseline for both variations of $k$.
Additionally, AdaTrace DP and PrivTrace also exhibit to be slightly better for
$k=3$.

matched

routed

(a) raw

(b) AdaTrace

(c) PrivTrace

(d) BiLSTM

Basemap: OpenStreetMap contributors

Figure 4. Example intersection showing the top five traffic movements for each
matched and routed dataset without DP. Line thickness represents the number of
trips.

Once again, it is evident that the adaptive grid performs better than the
static grid used by BiLSTM. The spatial distribution of matched trips (refer
to Appendix 6.3) also reflects the visual characteristics of the grid.
Although a similar distribution can be observed as in the raw data, there are
numerous turns and edges. Employing a finer grid to project the training data
could enhance the results.

Table 6. Averaged nDCG for traffic flow retrieval at 10 intersections, computed for $k=3$ and $k=5$. An nDCG of 1 signifies perfect retrieval. Bold font represents the superior value between the matched and routed versions for each comparison. | k=3 | k=10
---|---|---
| matched | routed | matched | routed
raw | 1.00 | 0.51 | 1.00 | 0.54
AdaTrace | 0.58 | 0.47 | 0.57 | 0.51
AdaTrace(DP) | 0.51 | 0.49 | 0.53 | 0.53
PrivTrace | 0.47 | 0.46 | 0.48 | 0.50
PrivTrace(DP) | 0.34 | 0.37 | 0.36 | 0.37
BiLSTM | 0.34 | 0.49 | 0.39 | 0.51

To assess the practical significance of the results, we analyzed the
distribution of nDCG values, visualized in Figure 5. The routed version of
BiLSTM outperforms the matching on almost all intersections. Even for the top-
performing AdaTrace, matching outperforms routing only in 6 out of 10
instances. Additionally, in half of the cases, the nDCG scores for ‘matched’
results are equal to or below 0.5. These findings highlight that while certain
intersections may exhibit accurate traffic flow representation, there remains
a 50% likelihood of erroneous outcomes. Consequently, the practical utility of
the results becomes limited.

(a) AdaTrace

(b) PrivTrace

(c) BiLSTM

Figure 5. Traffic flow retrieval according to nDCG with $k=3$: each point
corresponds to one intersection for selected models. Points above (below) the
diagonal indicate a superior routed (matched) value.

##  6\. Discussion and Conclusion

The potential of synthetic data lies in its (promised) ability to provide full
flexibility in analyses and modeling endeavors while ensuring a high level of
privacy. In our research, we delved into the practical implications of ‘full
flexibility’ for trip data consisting of fine-granular routes as typically
recorded using GPS devices.

To address the question of what constitutes high utility for trip data and how
it can be measured (RQ1), we assert that the metrics employed should
prioritize the detailed, sequential nature of trip data. Our proposal suggests
evaluating the lengths of trips, traffic volumes, preferences for specific
road segments, and the flow of traffic at intersections (in addition to
standard high-level metrics already used in the literature). These
measurements (along with the utilization of synthetic trip data at the street
level) necessitate an additional computationally intensive step known as ‘map
matching’. We further contend that synthetic data must surpass those generated
by standard routing algorithms in order to claim a significant advantage for
subsequent analyses.

It is worth noting that the models examined in this study, similar to the
majority of models used for generating synthetic mobility data, largely
exclude attributes that are crucial for real-life applications, such as
timestamps, traffic mode, and user-level information. This particularly
includes the inability to group trips per user. This limitation restricts the
potential applications of synthetic data to spatial information alone, which
prompted the consideration of the aforementioned metrics.

We evaluated the utility of five state-of-the-art models, AdaTrace, PrivTrace,
DP-Loc, a BiLSTM-based model, and TrajGAIL, using the designated utility
metrics on a dataset comprising approximately 30,000 bicycle trips in Berlin.
Regarding RQ2, we observed that TrajGAIL failed to generate data within a
reasonable computation time for city-scale scenarios, while DP-Loc frequently
generated jumps that were unsuitable for map matching. The remaining three
models maintained a certain degree of spatial distribution, as evidenced by
the analysis of road preferences. AdaTrace showed overall the best results. It
allowed survey participants to identify preferred roads with 90% accuracy and
an F1-score of $\geq 0.7$. Additionally, both AdaTrace and PrivTrace slightly
outperformed the routing baseline in analyzing traffic volumes. The adaptive
grid employed likely succeeds in maintaining ‘hotspots’ of the spatial
distribution. The BiLSTM-based model might potentially yield superior results
if trained on a grid with a finer resolution and a sufficiently large dataset.
However, the resulting increase in computational cost raises concerns
regarding its practical feasibility. Overall, the BiLSTM results remain
inconclusive since, contrary to the findings regarding traffic volumes on road
segments, it performed best in terms of statistical similarity of road
preferences and achieved results similar to AdaTrace in human classification
of road preferences. This underscores the need to consider multiple metrics as
a reliable measure of the success of arbitrary downstream tasks related to the
respective distribution.

Additionally, we found unsatisfactory utility when evaluating the ratio of
trip length to straight-line distance, with clear superiority of the routing
baseline for all models. With respect to traffic flow at intersections, only
AdaTrace managed to surpass the routing baseline substantially among the
evaluated models, but even then, the provided level of utility remained
questionable.

With regards to (RQ3), only AdaTrace and PrivTrace generated useful
differentially private data. As the application of a BiLSTM without DP raises
major privacy issues (Luca et al., 2021), further improvements are needed for
it to serve as a sensible privacy technique. Notably, despite increasing
AdaTrace’s spatial resolution from the default setting of $6x6$ to a more-
detailed $28x28$ top-level grid, the DP version still provided superior
results compared to PrivTrace without DP. It also outperformed the BiLSTM
model in two analyses and was only slightly inferior in two other evaluations.
However, the practical utility remains doubtful. In addition, it should be
noted that all evaluated models only offer item-level DP as user IDs are
discarded. This raises concerns about the provided privacy level, particularly
if only few power users contribute a significant portion of the data.

We further acknowledge that there may be more suitable map matching algorithms
for synthetic data than the utilized OSRM implementation. However, we rather
suggest the advancement of synthesis algorithms such that road networks are
inherently considered instead of optimizing post-processing techniques.

The SimRa dataset employed in this study is of significant importance from an
urban planning point of view, given its representation of a substantial number
of bicycle trips and riders’ perceived safety. While the evaluation on other
datasets that differ regarding size, city structure or traffic modes might
vary to a certain extent, we expect the overarching trends to remain
consistent. We aim to broaden our analyses in subsequent research to further
explore the models’ suitability, especially for taxi trips and larger
datasets.

In summary, our results raise the question of whether models claiming high
flexibility truly provide sufficient benefits or, on the contrary, may do more
harm by failing to deliver reliable results. If such models merely manage to
maintain a moderate level of spatial granularity, there might be more accurate
and privacy-preserving methods available through the provision of aggregate
data. It is likely that generating synthetic data offering both high
flexibility and strong privacy guarantees is not possible (Stadler and
Troncoso, 2022). Instead of striving for full flexibility, it is advisable to
clearly indicate the specific applications for which the respective model is
well-suited and those for which it is not. For instance, synthetic trip data
could prove valuable for development purposes or to gain a preliminary
understanding of raw data before utilizing it in a controlled and secure
environment for actual analyses. In such cases, the focus may be on
maintaining the sampling rate and accuracy of GPS data rather than precisely
mimicking the actual spatial distributions. For such applications, it may be
more important to retain all attributes instead of solely focusing on spatial
information.

## References

  * (1)
  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep Learning with Differential Privacy. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ _(CCS ’16)_. Association for Computing Machinery, New York, NY, USA, 308–318.  https://doi.org/10.1145/2976749.2978318
  * Bermbach (2021) David Bermbach. 2021\.  SimRa Rides Berlin 06/19 - 12/20.  (Feb. 2021).  https://doi.org/10.14279/DEPOSITONCE-10605
  * Bermbach and Karakaya (2021) David Bermbach and Ahmet-Serdar Karakaya. 2021.  SimRa Rides Berlin 01/21 - 09/21.  (Oct. 2021).  https://doi.org/10.14279/DEPOSITONCE-12452
  * Blanco-Justicia et al. (2022) Alberto Blanco-Justicia, Najeeb Moharram Jebreel, Jesús A. Manjón, and Josep Domingo-Ferrer. 2022\.  Generation of Synthetic Trajectory Microdata from Language Models. In _Privacy in Statistical Databases_ _(Lecture Notes in Computer Science)_ , Josep Domingo-Ferrer and Maryline Laurent (Eds.). Springer International Publishing, Cham, 172–187.  https://doi.org/10.1007/978-3-031-13945-1_13
  * Broach et al. (2012) Joseph Broach, Jennifer Dill, and John Gliebe. 2012.  Where Do Cyclists Ride? A Route Choice Model Developed with Revealed Preference GPS Data.  _Transportation Research Part A: Policy and Practice_ 46, 10 (Dec. 2012), 1730–1740.  https://doi.org/10.1016/j.tra.2012.07.005
  * Choi et al. (2021) Seongjin Choi, Jiwon Kim, and Hwasoo Yeo. 2021.  TrajGAIL: Generating Urban Vehicle Trajectories Using Generative Adversarial Imitation Learning.  _Transportation Research Part C: Emerging Technologies_ 128 (2021), 103091\.  https://doi.org/10.1016/j.trc.2021.103091
  * Dwork (2006) Cynthia Dwork. 2006\.  Differential Privacy. In _Automata, Languages and Programming_ _(Lecture Notes in Computer Science)_ , Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (Eds.). Springer, Berlin, Heidelberg, 1–12.  https://doi.org/10.1007/11787006_1
  * Dwork and Roth (2014) Cynthia Dwork and Aaron Roth. 2014.  _The Algorithmic Foundations of Differential Privacy_.
  * Gursoy et al. (2018) Mehmet Emre Gursoy, Ling Liu, Stacey Truex, Lei Yu, and Wenqi Wei. 2018.  Utility-Aware Synthesis of Differentially Private and Attack-Resilient Location Traces. In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_. 196–211.  https://doi.org/10.1145/3243734.3243741
  * He et al. (2015) Xi He, Graham Cormode, Ashwin Machanavajjhala, Cecilia M. Procopiuc, and Divesh Srivastava. 2015\.  DPT: Differentially Private Trajectory Synthesis Using Hierarchical Reference Systems.  _Proceedings of the VLDB Endowment_ 8, 11 (2015), 1154–1165.  https://doi.org/10.14778/2809974.2809978
  * Kapp (2022) Alexandra Kapp. 2022\.  Collection, Usage and Privacy of Mobility Data in the Enterprise and Public Administrations.  _Proceedings on Privacy Enhancing Technologies_ 2022, 4 (Oct. 2022), 440–456.  https://doi.org/10.56553/popets-2022-0117
  * Karakaya and Bermbach (2022) Ahmet-Serdar Karakaya and David Bermbach. 2022.  SimRa Rides Berlin 10/21 - 09/22.  https://doi.org/10.14279/DEPOSITONCE-16439
  * Karakaya et al. (2020) Ahmet-Serdar Karakaya, Jonathan Hasenburg, and David Bermbach. 2020.  SimRa: Using Crowdsourcing to Identify near Miss Hotspots in Bicycle Traffic.  _Pervasive and Mobile Computing_ 67 (Sept. 2020), 101197\.  https://doi.org/10.1016/j.pmcj.2020.101197
  * Lestyán et al. (2022) Szilvia Lestyán, Gergely Ács, and Gergely Biczók. 2022.  In Search of Lost Utility: Private Location Data.  _Proceedings on Privacy Enhancing Technologies_ 2022, 3 (2022), 354–372.  https://doi.org/10.56553/popets-2022-0076
  * Li et al. (2010) Xiaojie Li, Xiang Li, Daimin Tang, and Xianrui Xu. 2010\.  Deriving Features of Traffic Flow around an Intersection from Trajectories of Vehicles. In _2010 18th International Conference on Geoinformatics_. 1–5.  https://doi.org/10.1109/GEOINFORMATICS.2010.5567483
  * Lu et al. (2018) Wei Lu, Darren M. Scott, and Ron Dalumpines. 2018.  Understanding Bike Share Cyclist Route Choice Using GPS Data: Comparing Dominant Routes and Shortest Paths.  _Journal of Transport Geography_ 71 (July 2018), 172–181.  https://doi.org/10.1016/j.jtrangeo.2018.07.012
  * Luca et al. (2021) Massimiliano Luca, Gianni Barlacchi, Bruno Lepri, and Luca Pappalardo. 2021.  A Survey on Deep Learning for Human Mobility.  _ACM Computing Surveys (CSUR)_ 55, 1 (2021), 1–44.
  * Luxen and Vetter (2011) Dennis Luxen and Christian Vetter. 2011.  Real-Time Routing with OpenStreetMap Data. In _Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_ _(GIS ’11)_. ACM, New York, NY, USA, 513–516.  https://doi.org/10.1145/2093973.2094062
  * Prato (2009) Carlo Giacomo Prato. 2009\.  Route Choice Modeling: Past, Present and Future Research Directions.  _Journal of Choice Modelling_ 2, 1 (Jan. 2009), 65–100.
  * Stadler and Troncoso (2022) Theresa Stadler and Carmela Troncoso. 2022.  Why the Search for a Privacy-Preserving Data Sharing Mechanism Is Failing.  _Nature Computational Science_ 2, 4 (2022), 208–210.  https://doi.org/10.1038/s43588-022-00236-x
  * Sun et al. (2023) Xinyue Sun, Qingqing Ye, Haibo Hu, Yuandong Wang, Kai Huang, Tianyu Wo, and Jie Xu. 2023.  Synthesizing Realistic Trajectory Data With Differential Privacy.  _IEEE Transactions on Intelligent Transportation Systems_ (2023), 1–14.
  * Wang et al. (2023) Haiming Wang, Zhikun Zhang, Tianhao Wang, Shibo He, Michael Backes, Jiming Chen, and Yang Zhang. 2023.  PrivTrace: Differentially Private Trajectory Synthesis by Adaptive Markov Model. In _USENIX Security Symposium 2023_.
  * Wei et al. (2020) Hua Wei, Guanjie Zheng, Vikash Gayah, and Zhenhui Li. 2020\.  A Survey on Traffic Signal Control Methods.  (Jan. 2020).  arXiv:1904.08117 [cs, stat]

## Appendix

###  6.1. Map matching validity

There are cases in which the matching API is not suitable for capturing
actually traveled bicycle routes. Figure 6 provides examples of potential
issues.

Basemap: OpenStreetMap contributors

original tracematched trace

Figure 6. Examples of map matching inaccuracies. Left: A cyclist used a
footpath that was matched to a legally accessible path. Center: Start or end
of the trace is off the road network - in this example, at a train station.
Right: Matching terminates when there is no nearby path available - here, a
cyclist rides on an uncharted path in a park.

Also, it is possible for the API to entirely fail in producing a matched
trace. A solid map matching is crucial for ensuring the validity of our
results. Thus, we assess the frequency of complete matching failures and
matched trips shorter than 90% of their original counterpart, indicating
termination in the midst of the trace. Table 7 suggests that for all datasets,
matching entirely fails only for at most $4\%$ of trips and partly for $18\%$,
which is acceptable for the purposes of our evaluation.

Table 7. Percentage of completely and partly failed matches per dataset. | failed (%) | shorter (%)
---|---|---
raw | 0 | 7
AdaTrace | 1 | 5
AdaTrace DP | 1 | 13
PrivTrace | 2 | 6
PrivTrac DP | 4 | 5
BiLSTM | 0 | 18

To further assess the validity of the chosen matching algorithm, we evaluate
the map matching using the Hausdorff distance. In an accurate map matching
scenario, the Hausdorff distance should be small, indicating that no points in
the matched trip are far away from their corresponding point in the original
trip. As expected for successful map matching, all synthetic datasets show a
Hausdorff distance in the order of magnitude of the selected grid resolution,
and the raw data has a median Hausdorff distance of only $33m$.

###  6.2. Original dataset visualization

Figure 7 visualizes the original datasets without DP with respect to their
spatial distribution as well as example trips.

(a) raw

(b) AdaTrace

(c) PrivTrace

(d) BiLSTM

Basemap: OpenStreetMap contributors

Figure 7. Spatial distribution (left) of original datasets without DP and
respective example trips (right).

###  6.3. Matched and routed spatial distributions

Figure 8 shows spatial distributions for each dataset without DP in matched
and routed versions.

(a) raw

(b) AdaTrace

(c) PrivTrace

(d) BiLSTM

Figure 8. Spatial distribution of matched (left) and routed (right) datasets
without DP.