#  $\mathsf{LDPTrace}$: Locally Differentially Private Trajectory Synthesis

Yuntao Du  Purdue University<EMAIL_ADDRESS>,  Yujia Hu  Zhejiang University
<EMAIL_ADDRESS>,  Zhikun Zhang  CISPA<EMAIL_ADDRESS>,  Ziquan
Fang  ,  Lu Chen  Zhejiang University<EMAIL_ADDRESS>,  Baihua Zheng
Singapore Management University<EMAIL_ADDRESS>and  Yunjun Gao  Zhejiang
University<EMAIL_ADDRESS>
###### Abstract.

Trajectory data has the potential to greatly benefit a wide-range of real-
world applications, such as tracking the spread of the disease through
people’s movement patterns and providing personalized location-based services
based on travel preference. However, privacy concerns and data protection
regulations have limited the extent to which this data is shared and utilized.
To overcome this challenge, local differential privacy provides a solution by
allowing people to share a perturbed version of their data, ensuring privacy
as only the data owners have access to the original information. Despite its
potential, existing point-based perturbation mechanisms are not suitable for
real-world scenarios due to poor utility, dependence on external knowledge,
high computational overhead, and vulnerability to attacks. To address these
limitations, we introduce $\mathsf{LDPTrace}$, a novel locally differentially
private trajectory synthesis framework. Our framework takes into account three
crucial patterns inferred from users’ trajectories in the local setting,
allowing us to synthesize trajectories that closely resemble real ones with
minimal computational cost. Additionally, we present a new method for
selecting a proper grid granularity without compromising privacy. Our
extensive experiments using real-world data, various utility metrics and
attacks, demonstrate the efficacy and efficiency of $\mathsf{LDPTrace}$.

PVLDB Reference Format:
PVLDB, 16(8): 1897 - 1909, 2023.
doi:10.14778/3594512.3594520 ††This work is licensed under the Creative
Commons BY-NC-ND 4.0 International License. Visit
https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this
license. For any use beyond those covered by this license, obtain permission
by emailing<EMAIL_ADDRESS>Copyright is held by the owner/author(s).
Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 16, No. 8 ISSN 2150-8097.
doi:10.14778/3594512.3594520

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/zealscott/LDPTrace.

##  1\. Introduction

The widespread availability of location sensing technology, such as GPS, has
revolutionized our ability to collect real-time data. As a result, there has
been significant interest in studying human mobility patterns on a large scale
for a variety of location-based applications, including traffic prediction,
route planning, and recommendation. Despite the immense value of this data,
privacy concerns surrounding the sensitive nature of trajectories have limited
its use.

Differential privacy (DP) has become the de facto standard for protecting
sensitive data while ensuring individual privacy. Despite the development of
various DP algorithms for trajectory publishing and analysis, these methods
rely on a _trustworthy aggregator_ to collect users’ raw trajectories. In
contrast, local differential privacy (LDP) allows users to directly share a
noisy version of their data, reducing the risk of data breaches from
untrustworthy data curators.

The LDP provides a more practical setting and improved privacy properties,
however, it imposes challenges in preserving the complex spatial patterns of
trajectories due to its strict privacy requirements. Currently, the only
solution that meets the rigorous privacy requirement of LDP is
$\mathsf{NGRAM}$ (Cunningham et al., 2021b). This method uses the exponential
mechanism to directly perturb individual trajectory in the local setting and
leverages external knowledge (POIs, business opening hours, _etc._) and
overlapped n-grams to enhance the realism of the noisy trajectories. However,
$\mathsf{NGRAM}$ has several major limitations that hinder its effectiveness:

  * •

Poor global utility. As $\mathsf{NGRAM}$ only focuses on local trajectory
proximity for utility optimization (similarity between original and perturbed
trajectories), it results in poor global utilities, as reported in Section
6.3. Most location-based applications rely on population-level spatial
statistics (_e.g.,_ range query and spatial density) and moving patterns
(_e.g.,_ distribution of start/end points and frequent travel patterns),
rather than individual behaviors (_e.g.,_ routing preference), and the failure
to preserve global utility significantly limits its applications.

  * •

Dependence on auxiliary knowledge. The performance of $\mathsf{NGRAM}$ heavily
relies on external knowledge (_e.g.,_ POI categories and business opening
hours), which may not always be accessible and can become outdated easily.
This leads to a dramatic decrease in utility and authenticity of generated
trajectories. In addition, users are required to store the external data on
their own devices, which is highly impractical for wearable or low-cost GPS
devices with limited storage.

  * •

High computational overhead. To obtain accurate perturbed trajectories,
$\mathsf{NGRAM}$ uses linear programming solvers, which are time-consuming and
require pre-processing to deal with external knowledge (_e.g.,_ POI processing
and hierarchical decomposition). This can result in significant delays for
users, reducing their satisfaction with location-based services.

  * •

Vulnerable to attacks. Point-based privacy mechanisms are vulnerable to
location-based attacks, such as re-identification attack (Montjoye et al.,
2013; Xiao and Xiong, 2015) and outlier leakage (Gursoy et al., 2018b; Jin et
al., 2022b), due to the strong statistical correlation between the fake
locations and user’s true locations. This is even more concerning for
$\mathsf{NGRAM}$ as it leverages external knowledge to maintain geographic and
semantic similarities between real and perturbed points in the local setting
(as to be detailed in Section 6.8). As a result, alternative attack-resilient
approaches must be sought to address privacy concerns.

The existing shortcomings motivate us to develop a new local privacy-
preserving paradigm that is both utility-aware and efficient. Instead of
perturbing each trajectory individually, we aim to extract the key movement
patterns of each user and use them to synthesize privacy-preserving and
realistic trajectories. However, synthesizing trajectories in the local
setting is _challenging_ due to the following two reasons. First, previous
trajectory synthesis methods either rely on global statistical metrics
(Bindschaedler and Shokri, 2016; Gursoy et al., 2018b) or spatial-aware data
structures (_e.g.,_ prefix tree (Chen et al., 2012b; He et al., 2015)) to
model the spatial distributions. However, these are not feasible in local
settings as there is no trusted data curator to collect these information and
it is infeasible to directly collect the statistics from individual users, who
typically only have a few trajectory footprints, leading to severely biased
estimations. Second, existing LDP methods assume that each individual holds a
single data record (_e.g.,_ a single value) (Wang et al., 2017a; Cormode et
al., 2018), but this assumption is no longer valid for trajectory data, which
is a sequence of spatial points with timestamps and has complex spatial
context that cannot be simply modeled by the methods.

Therefore, we present $\mathsf{LDPTrace}$, a simple yet effective framework
for synthesizing locally differentially private and attack-resistant
trajectories. $\mathsf{LDPTrace}$ achieves the following four objectives: (i)
robust, rigorous statistical privacy, (ii) flexibility and low computational
cost, (iii) strong preservation of global spatial utilities and authenticity,
and (iv) deterministic resilience against trajectory privacy attacks.
Specifically, $\mathsf{LDPTrace}$ approaches trajectory synthesis as a
generative process, constructing a probabilistic model based on users’
transition records to estimate the global moving patterns. The transition
records capture the spatial relationship between adjacent points, while
remaining low computational complexity. To enhance the authenticity of
synthesized trajectories, $\mathsf{LDPTrace}$ includes virtual start and end
points to each trajectory in the generation process to indicate the beginning
and terminated transition states. Additionally, the framework estimates the
trajectory length distribution for optimal transition budget allocation and
deterministic generation constraints. We also provide a theoretical guideline
for selecting grid granularity without consuming privacy budget. Last but not
the least, an adaptive synthesis algorithm is employed to generate realistic
trajectories without access to users’ real trajectories.

Our synthetic trajectory generation process is locally differentially private,
meaning that the global moving patterns are not strongly dependent on any
specific user and the generation of synthetic trajectory is not bias towards
any specific trajectory. We have conducted an extensive experimental
evaluation to compare $\mathsf{LDPTrace}$ with the state-of-the-art method
$\mathsf{NGRAM}$. Experimental results indicate that $\mathsf{LDPTrace}$
significantly outperforms the competitor in terms of data utility, efficiency,
and scalability, and it is equipped with robust resistance against various
location-based attacks for superior privacy protection.

In summary, the key contributions of our work are below.

  * •

We propose $\mathsf{LDPTrace}$, the first trajectory synthesis solution with
local differential privacy guarantee that is able to generate realistic
trajectories without any external knowledge.

  * •

We introduce a neat and effective framework that collects key moving patterns
from users’ trajectories with little computational cost, and devise an
adaptive synthesis algorithm to generate authentic trajectories.

  * •

We perform comprehensive analysis on the errors and complexity of the proposed
framework, and present a guideline for selecting the grid granularity without
consuming privacy budget.

  * •

We conduct extensive experiments to demonstrate the superiority of
$\mathsf{LDPTrace}$ in terms of utility, efficiency, and scalability.
Moreover, we show that $\mathsf{LDPTrace}$ is able to resist various location-
based attacks.

The rest of this paper is organized as follows. We review related work in
Section 2, and elaborate our motivation in Section 3. Then, we present
preliminaries in Section 4. Section 5 details the proposed synthesis
framework. The experimental results are reported in Section 6. Finally, we
conclude the paper, and offer directions for future work in Section 7.

##  2\. Related Work

Differential privacy (DP) (Dwork, 2006) has become the de facto privacy
standard. While centralized DP assumes data aggregators are reliable, local
differential privacy (LDP) (Duchi et al., 2013) assumes that aggregators
cannot be trusted and relies on data providers to perturb their own data.
Early studies (Li et al., 2012, 2013; Bassily et al., 2017; Wang et al.,
2017b; Johnson et al., 2018; Gu et al., 2019; Cormode et al., 2021; Li et al.,
2020) on DP and LDP mostly focus on designing tailored algorithms for specific
data analysis tasks, which suffers from poor flexibility, inefficiency, and
scalability problems. One promising solution (Zhang et al., 2021; Cai et al.,
2021; Ge et al., 2021; Zhang et al., 2018; Yuan et al., 2023) to address this
problem is generating a synthetic dataset that is similar to the private
dataset while satisfying (local) differential privacy. However, these methods
mainly aim at structured data like tables, which cannot be applied to
trajectory data due to its high dimensionality and complex spatial dependence.

The privacy of trajectory data (surveyed in (Jiang et al., 2021; Jin et al.,
2022a)) has been a significant concern for over a decade and various solutions
have been proposed to address the issue. Many existing solutions (Bonomi and
Xiong, 2013; Andrés et al., 2013; Jin et al., 2022b; Zeighami et al., 2022;
Weggenmann and Kerschbaum, 2021; Acs and Castelluccia, 2014; Cao et al., 2017)
employ spatial point perturbation techniques under the constraint of DP that
add noises to the point locations of trajectory before it is published or used
to answer predefined queries (_e.g.,_ range query). For example, GL (Jin et
al., 2022b) aims to preserve both privacy and high utility by perturbing the
local/global frequency distributions of important locations in a trajectory.
SNH (Zeighami et al., 2022) introduces a neural database for spatial range
queries and adds DP-compliant noise to the input queries to maintain the
density features of location data. More recently, $\mathsf{NGRAM}$ (Cunningham
et al., 2021b) has been proposed to address the privacy concerns of trajectory
sharing in a local setting. The method includes three phases: (1) hierarchical
decomposition phase, where POIs are divided into spatial-temporal-category
regions; (2) perturbation phase, where trajectories are converted to sequences
of overlapping n-grams and perturbed using exponential mechanism; and (3)
reconstruction phase, where $\mathsf{NGRAM}$ solves an optimization problem to
reconstruct the continuous trajectory based on the perturbed n-grams. Despite
its efforts, $\mathsf{NGRAM}$ still has several limitations, such as low
global utility, high computational overhead, and vulnerability to attacks.

To protect privacy, some researchers have investigated alternative methods to
point perturbation, such as generating synthetic trajectories (Chen et al.,
2012b; He et al., 2015; Bindschaedler and Shokri, 2016; Gursoy et al., 2018a,
b; Cunningham et al., 2021a; Gursoy et al., 2020; Yang et al., 2022). The
challenge is to create synthetic data that resembles genuine user traces while
providing practical privacy protection. One approach, DPT (He et al., 2015),
uses a hierarchical reference system to model trajectory movements at
different speeds and encodes transitions between grid cells using prefix
trees. By injecting Laplace noise to the prefix trees, the transition
probabilities are distorted while still maintaining the movement patterns of
the original traces. Further studies (Bindschaedler and Shokri, 2016; Gursoy
et al., 2018a) have extended DPT by incorporating trajectory semantics and
temporal information. Another method, AdaTrace (Gursoy et al., 2018b),
extracts four statistical and spatial features and incorporates them into its
private synopsis, including a density-aware grid, Markov mobility model,
pickup/destination and length distribution. The authors also design a
synthesizer with attack resilience constraints to balance both statistical
privacy (differential privacy) and syntactic privacy (attack resilience).
PrivTrace (Wang et al., 2023) applies an adaptive strategy to choose crucial
first- and second-order Markov transitions for trajectory synthesis, resulting
in better utilities than previous methods. Although current synthetic methods
are effective, they all rely on a trustworthy data curator to aggregate useful
statistics. Our work is the first to introduce an utility-aware and efficient
trajectory synthesis framework without accessing users’ real traces.

##  3\. Motivation

Trajectory is a time-order sequence of location points generated from human
mobility, which is highly sensitive since it can reveal people’s home/work
place, travel patterns, and other preferences. The population level aggregate
spatial information on where/when do residents commute could be useful for the
authority to gain better understanding of residents’ commuting patterns, but
many people are unwilling to share their own trajectories because of privacy
concerns. Therefore, we aim to propose a method for various parties (e.g.,
authority/service providers) to collect useful mobility patterns from crowd
without accessing individual’s real trajectories. In the following, we present
four critical design principles that motivate and guide our solution,
including _privacy protection_ , _global utility_ , _practicability and
efficiency_ , and _attack resilience_.

Privacy protection. The primary goal of our work is to protect each
individual’s privacy so that the untrusted data curator cannot access people’s
real traces. We achieve this by utilizing LDP mechanism to perturb user’s
trajectories before sharing the data. We detail the privacy implications of
our method in Section 5.7.

Global utility. Based on the rigorous privacy guarantee of LDP, our solution
is expected to be designed in such a way that it can preserve the high global
utility for synthetic trajectories. We argue that a feasible way to boost
global utility is to extract the key moving patterns from user’s trajectories,
and leverage these information to guide the synthesis process. Since the
synthesizer is designed to capture the intrinsic features of user’s movements,
the synthetic trajectories can be used for various spatial analysis tasks like
range query and frequent pattern mining, instead of tailor-made for specific
utility like (Cunningham et al., 2021b).

Practicability and efficiency. Considering the wide usage of trajectory data,
our solution is preferred to be as simple as possible so that it can be easily
deployed to any local devices without heavy computation. Besides, it is
equally critical to ensure the efficiency, thus privacy and utility do not
come at the cost of user experience.

Attack resilience. Although LDP is a strong data sharing technique with
provable privacy guarantees, it still suffers from various syntactic attacks.
This is especially true for trajectory privacy protection, as blindly forcing
the perturbed trajectories to resemble original ones would make them
vulnerable to various location-based attacks like re-identification attack and
outlier leakage. Hence, the synthetic trajectories should be robust, and they
are expected to be able to resist common attacks.

Applications. Our work focuses on synthesizing trajectories such that the
global aggregate statistics is preserved as much as possible, which is
essential to many important location-based applications. A notable one is
trajectory monitoring that identifies people’s movement patterns, which can be
used for policy making decisions like traffic control or disease spread
forecasting (like Covid-19). Other applications include location-based
services and advertising, _e.g.,_ a tourism recommendation system can utilize
common trajectories taken by people to recommend popular trips/destinations,
and an outdoor advertising company can use people’s movement patterns to
better estimate the traffic flows at different locations.

Table 1. Symbols and Description

Notation | Description
---|---
$T$, $\mathcal{T}$ | Trajectory, and a set of trajectories
$C$, $\mathcal{C}$ | Grid cell, and a set of grid cells
$L$, $\mathcal{L}$ | Trajectory length, length distribution
$s$, $\mathcal{S}$ | Intra-trajectory transition, mobility model
$M$, $\mathcal{M}$ | Aggregated transition, aggregated mobility model
$C_{a}$, $C_{b}$ | Virtual start/end point
$\mathcal{N}$, $\mathcal{N}^{*}$ | Neighborhood cells without/with virtual end point
$\hat{g}(\cdot)$, $\tilde{g}(\cdot)$ | Report times, unbiased estimation of frequency
$\epsilon$ | Privacy budget

##  4\. Preliminaries

In this section, we first introduce the definition of local differential
privacy (LDP) and then formulate our problem. Table 1 lists the notations used
in this paper.

###  4.1. Differential Privacy in the Local Setting

####  4.1.1. $\epsilon$-Local Differential Privacy.

In the local setting of DP, there are many users and one untrusted aggregator,
and each user perturbs the input value $x$ using an algorithm $\Psi$ and sends
$\Psi(x)$ to the aggregator. The formal privacy requirement is that the
algorithm $\Psi(\cdot)$ satisfies the following property:

###### Definition 0 ($\epsilon$-Local Differential Privacy).

An algorithm $\Psi(\cdot)$ satisfies $\epsilon$-local differential privacy
($\epsilon$-LDP), where $\epsilon\geq 0$, if and only if for any input
$x_{1}$, $x_{2}$ and output $y$:

(1) $Pr[\Psi(x_{1})=y]\leq e^{\epsilon}Pr[\Psi(x_{2})=y].$

The privacy budget $\epsilon$ is a metric used to measure the level of privacy
protection in local differential privacy (LDP). It represents the probability
that an attacker can determine the true value of the input based on the
output. The higher the privacy budget, the higher the probability that the
attacker can infer the true value, and the lower the privacy protection. In
practice, the privacy budget can be set according to the privacy requirements
of the application. For example, a smaller privacy budget may be chosen when
collecting highly sensitive data such as health information, while a larger
privacy budget may be used for less sensitive data such as typing patterns. A
privacy budget of less than 2 is typically considered acceptable (Erlingsson
et al., 2014; Jin et al., 2022b; Ding et al., 2017; Wang et al., 2017a;
Zeighami et al., 2022; Cunningham et al., 2021b; Wang et al., 2021; Du et al.,
2021). LDP provides privacy protection by allowing the user to report a
perturbed version of the input $\Psi(x)$ instead of the true value $x$ to the
aggregator. This ensures that even if the aggregator is malicious, the user’s
privacy is still protected. LDP possesses two fundamental properties used in
our mechanism (Cormode et al., 2018): the composition theorem, which states
that $k$ $\epsilon_{i}$-LDP mechanisms can be combined to achieve
$\epsilon$-LDP protection, where $\epsilon=\sum_{i}\epsilon_{i}$; and the
ability to perform post-processing on private outputs without affecting the
privacy guarantee. For more information on LDP, please refer to recent surveys
(Cormode et al., 2018; Xiong et al., 2020; Yang et al., 2020).

####  4.1.2. Optimized Unary Encoding.

A frequency oracle (FO) protocol enables the estimation of the frequency of
any value $x$, which serves as a building block of many LDP tasks. In this
paper, we opt for Optimized Unary Encoding (OUE) as the FO protocol to achieve
frequency estimation under LDP, which consists of three stages: encoding,
perturbing, and aggregation (Wang et al., 2017a).

  * •

Encoding. The original value $x$ is first encoded as a length-$d$ binary
vector $V$, where only the $x$-th bit is set to 1, _i.e.,_
$V[i]=\mathbbm{1}(i==x)$.

  * •

Perturbing. When reporting the encoded vector $V$, it is perturbed as follows:

(2) $Pr[\hat{V}[i]=1]=\begin{cases}\frac{1}{2},&\text{if }V[i]=1\\\
\frac{1}{e^{\epsilon}+1},&\text{if }V[i]=0,\end{cases}$

where $\epsilon$ is the privacy budget and $\hat{V}$ is the reported noise
vector.

  * •

Aggregation. In order to obtain the unbiased estimation of the real value from
noise vectors, the data curator needs to aggregate and adjust the received
data as follows:

(3) $\tilde{g}(x)=\frac{\hat{g}(x)-nq}{\frac{1}{2}-q},\
q=\frac{1}{e^{\epsilon}+1},$

where $n$ is the total number of reported noise vectors, and $\hat{g}(x)$ is
the total number of the reported vectors $\hat{V}$ whose $x$-th bit is 1,
_i.e.,_ $\hat{g}(x)=|\\{\hat{V}|\hat{V}[x]=1\\}|$. Notice that this adjustment
requires the budget $\epsilon$ to remain the same across all the reported
data.

It can be theoretically proved (Wang et al., 2017a) that the adjusted
estimation $\tilde{g}(x)$ is unbiased. The mean and variance of OUE are listed
below.

(4)
$\mathop{\mathrm{E}}[\tilde{g}(x)]=f_{x},\quad\mathop{\mathrm{Var}}[\tilde{g}(x)]=n\frac{4e^{\epsilon}}{(e^{\epsilon}-1)^{2}},$

where $f_{x}$ is the frequency of value $x$, and $\epsilon$ is the privacy
budget.

###  4.2. Problem Statement

Consider there is a collection of trajectories generated by mobile travelers
on the roads, denoted by $\mathcal{T}$. People are unwilling to report their
own trajectories to the untrusted data curator due to privacy concerns. Thus,
we want to build a generative model over $\mathcal{T}$ by extracting key
moving patterns from $\mathcal{T}$ with provable guarantees on individual
privacy. We then employ the generative model to output a set of synthesized
trajectories, denoted by $\mathcal{T}_{syn}$. The synthesized trajectories
$\mathcal{T}_{syn}$ should collectively retain a high resemblance to the real
trajectories $\mathcal{T}$, so that $\mathcal{T}_{syn}$ has many useful
statistical and spatial features in common with $\mathcal{T}$. Finally, the
synthetic trajectories $\mathcal{T}_{syn}$ should be robust against various
location-based attacks, in order to strengthen privacy by maximizing
attackers’ probability of errors in identifying the true traces of users.

##  5\. Our Methodology

In this section, we first give an overview of our proposed method
$\mathsf{LDPTrace}$, and discuss the necessity and method for trajectory
discretization. Then, we detail the three crucial components of
$\mathsf{LDPTrace}$, which are estimated from collaborative mobility patterns
and satisfy the strict privacy guarantee of LDP. Next, we detail the adaptive
generation process by building a probabilistic model with learned spatial
patterns. Finally, we conduct thorough discussion to analyze the privacy and
computational cost of $\mathsf{LDPTrace}$, and present an approach to select a
proper grid granularity.

Figure 1. The $\mathsf{LDPTrace}$ framework.

###  5.1. Solution Overview

As illustrated in Figure 1, both user and data curator participate in the
process of $\mathsf{LDPTrace}$. On the user side, $\mathsf{LDPTrace}$ first
discretizes the trajectory into a sequence of adjacent cells, and exacts three
key features of the trajectory by perturbing the trajectory length, intra-
trajectory mobility, and beginning/terminated transitions. On the data curator
side, $\mathsf{LDPTrace}$ collects the perturbed information (_i.e.,_ three
features mentioned earlier) from all users, and builds a probabilistic model
by estimating the key mobility features (_i.e.,_ length distribution and
aggregated transitions). Finally, $\mathsf{LDPTrace}$ performs the synthesis
to sample start point and subsequent transitions from the learned patterns,
with its termination controlled by the estimated trajectory length and sampled
end point.

Since the synopsis of $\mathsf{LDPTrace}$ consists of three features learned
from user’s trajectory, the security budget $\epsilon$ is divided into three
sub-budgets $\epsilon_{1}$, $\epsilon_{2}$, and $\epsilon_{3}$, such that
$\sum\nolimits_{i=1}^{3}\epsilon_{i}=\epsilon$. Detailed analysis on the
privacy is presented in Section 5.7.

###  5.2. Geospatial Discretization

The representation of a trajectory as a sequence of points in a continuous
two-dimensional domain, such as latitude-longitude coordinates, can be
challenging to model. To overcome this, one common approach is to discretize
the geographic space into grid cells. This is achieved by partitioning the
entire space into equal-sized cells using a grid granularity of $N$.

Each trajectory is then transformed into a sequence of enumerable cells,
$T=\\{C_{1},C_{2},\cdots,C_{|T|}\\}$, where $T[i]$ refers to the $i$-th cell
visited by the trajectory $T$ and $|T|$ is the length of the trajectory in
grid cells. The choice of $N$ affects the size of each grid cell, and thus the
granularity of the discretized trajectory.

When $N$ is small, the space is partitioned into a limited number of grid
cells, and each cell covers a large spatial region. Many points in the
original trajectory will be represented by one single cell, and thus, the
mobility patterns captured by the discretized trajectory would be very general
and uninformative. On the other hand, if $N$ is big, each grid cell covers a
very small region, resulting in the risk of having many empty cells that have
not been passed by any trajectories. Perturbing these empty cells leads to
high noise and inefficiency. While some literature (Qardaji et al., 2013;
Gursoy et al., 2018b) has provided guidelines for selecting a proper grid
granularity, they all rely on global statistics like spatial density, which
are typically not available in the local setting where a user only has access
to his/her own trajectories. Instead of estimating the global statistics which
costs extra privacy budget, we theoretically analyze the trade-off between
estimation errors and the granularity of grid cells, and propose a novel
method to choose $N$ in the local setting without consuming any budget, as to
be detailed in Section 5.9.

###  5.3. Trajectory Length Distribution

The first component in $\mathsf{LDPTrace}$ is the estimated length
distribution of trajectories, which is an indispensable character of
trajectory synthesis since it indicates the probabilistic travel distance of
users’ trace, and serves as the deterministic constraint to terminate the
synthesis process. However, estimating the length distribution is a non-
trivial task in the local setting since there is no aggregated statistics
available. Instead, we aim to collect the length information from each user
and approximate the distribution with frequency. Specifically, we first define
the domain of lengths as $|\mathcal{C}|$, under the assumption that the
maximum travel distance of any trajectory is $|\mathcal{C}|$. Note that the
techniques proposed in this paper can take any maximum distance as an input.

On the user side (③ in Figure 1), for trajectory $T$ with length $m$ (_i.e.,_
$|T|=m$), we encode it into a $|\mathcal{C}|$-bit binary vector $V$, which
sets only the $m$-th bit to 1 but all other bits to zero. Next, the binary
vector $V$ is perturbed individually and locally with budget $\epsilon_{1}$
according to Equation (2), and the user only reports the noisy vector
$\hat{V}$ to the untrusted data curator.

On the data curator side (④ in Figure 1), after collecting noisy vector
$\hat{V}$ from different users, the curator estimates the frequency of each
length value $m$ by counting the non-zero entry of each vector and adjusting
the total count of each length via the unbiased statistic using Equation (3).
Finally, we view the length distribution as the categorical distribution
$\mathcal{L}$, and the probability of length $m$ is
$Pr(m)=\tilde{g}(m)/\sum\nolimits_{i=1}^{|\mathcal{C}|}\tilde{g}(i)$, where
$\tilde{g}(m)$ is the unbiased OUE estimator of the true frequency of length
$m$.

Error analysis. We analyze the error of estimated length distribution
$\mathcal{L}$ by using the Theorem A.1 in Appendix A. $Pr(m)$ is the unbiased
estimator of length probabilities:

(5)
${\mathop{\mathrm{E}}}^{*}[Pr(m)]=f_{m}/\sum\nolimits_{i=1}^{|\mathcal{\mathcal{C}}|}f_{i},$

where $f_{i}$ is the frequency of trajectory length $i$ in the whole
trajectory set $\mathcal{T}$. Thus, the estimated length distribution
$\mathcal{L}$ approximates the true distribution with the error:

(6)
$\displaystyle\mathop{\mathrm{Error}}(\mathcal{L})=\sum\nolimits_{i=1}^{|\mathcal{C}|}(\frac{f_{i}}{|\mathcal{T}|})^{2}[\frac{\sigma^{2}}{(f_{i})^{2}}-\frac{2\sigma^{2}}{f_{i}|\mathcal{T}|}+\frac{8\sigma^{2}}{|\mathcal{T}|^{2}}],$

where
$\sigma^{2}=|\mathcal{T}|\frac{4e^{\epsilon_{1}}}{(e^{\epsilon_{1}}-1)^{2}}$
is the variance of OUE estimator in Equation (4), and $|\mathcal{T}|$ is the
number of trajectories. Given the fixed statistics of trajectories (e.g., size
and frequency of each length), the error of estimated length distribution
$\mathcal{L}$ is on the order of $e^{-\epsilon}$, _i.e.,_ a higher budget
could help reduce the length error.

###  5.4. Intra-Trajectory Mobility Model

To generate high utility and realistic synthetic trajectories, it is necessary
to mimic actual intra-trajectory mobility (_i.e.,_ the transition from $T[i]$
to $T[i+1]$). We achieve this by building a Markov chain for mobility
modelling. A first-order Markov chain asserts that a location $T[l+1]$ in a
trajectory depends only on its previous location $T[l]$ instead of all
previous locations:

(7) $Pr(T[l+1]=C~{}|~{}T[1]...T[l])=Pr(T[l+1]=C~{}|~{}T[l]),$

which simplifies the complex sequential dependency $T[1]...T[l]$ with closest
grid $T[l]$ for $T[l+1]$. We assume that the main mobility patterns of
trajectories can be captured by the Markov chain, which is a collection of
such probability $Pr(T[l+1]=C_{next}|T[l])$. Considering the continuity of
trajectories, we interpolate each trajectory to make sure that any two
consecutive points in a trajectory corresponding to two adjacent grid cells,
_i.e.,_ $T[i]$ is adjacent to $T[i+1]$. Accordingly, we can define the
transition state $s_{ij}$ from grid cell $C_{i}$ to another grid cell $C_{j}$
as follows:

(8) $Pr(s_{ij})=\begin{cases}Pr(T[l+1]=C_{j}~{}|~{}T[l]=C_{i}),&\text{if
}C_{j}\in\mathcal{N}_{C_{i}}\\\ 0,&\text{otherwise},\end{cases}$

where $Pr(s_{ij})$ is the transition probability from $C_{i}$ to $C_{j}$,
$\mathcal{N}_{C_{i}}$ captures the set of adjacent cells of $C_{i}$, and the
transition model $\mathcal{S}$ is a set of all transition probabilities
aggregated from trajectories.

Similar to the estimation of length distribution, we aim to collect the
transition information from each user (① in Figure 1) and then aggregate them
on the data curator side to estimate the overall transition states. Thus, each
user’s trajectory $T$ can be represented as a sequence of transition states
$S_{T}$ with length $|T|-1$. On the user side, for each state in $S_{T}$, we
also opt for OUE to encode it into a $|\mathcal{S}|$-bit binary vector and
then report the perturbed noisy version, where $|\mathcal{S}|$ is the domain
of possible states. Since we only consider transition between two adjacent
grids and each grid cell has up to 8 adjacent cells, we have
$|\mathcal{S}|\approx 8|\mathcal{C}|$.

However, if we directly perturb each trajectory’s transition by averaging the
privacy budget $\epsilon_{2}$ with its own length $|S_{T}|$, it is impossible
to estimate the unbiased frequency of each transition state $s$ from all
trajectories since OUE protocol demands the budget used to be same across
different users/trajectories. A straightforward solution to this problem is to
equally divide budget $\epsilon_{2}$ across $|\mathcal{C}|$, the maximum
length of $T$, meaning that each trajectory is allowed to have up to
$|\mathcal{C}|$ transitions, and each transition is assigned a budget of
$\epsilon_{2}/|\mathcal{C}|$. Nevertheless, this approach suffers from huge
waste of budget as the length of most trajectories could be far shorter than
$|\mathcal{C}|$. Therefore, we set the number of transitions as the $k$-th
quantile of estimated length distribution $L_{k}$, so that we only upload
$L_{k}$ transition states for all trajectories, and omit the remaining if the
number of transitions $|S_{T}|$ is longer than $L_{k}$. Here, $k$ is a
hyperparameter to balance the noise error and bias error. On one hand, we
would like $k$ to be large, _i.e.,_ every transition in trajectory data
$\mathcal{T}$ can be captured for modelling mobility patterns, and the amount
of noise added to state $s$ can be measured by:

(9)
$N(s,\epsilon_{2},L_{k})={\mathop{\mathrm{Var}}}^{*}[Pr(s),\epsilon_{2}/L_{k}],$

where $\mathop{\mathrm{Var}}^{*}(Pr(s),\epsilon_{2}/L_{k})$ is the
approximated variance of transition probability $Pr(s)$ with budget
$\epsilon_{2}/L_{k}$, which can be calculated via Theorem A.1. On the other
hand, omitting the transitions for trajectories with length longer than
$L_{k}$ will introduce bias into the model (_i.e.,_ some of the transitions
are not accurately captured), and the bias of transition $s$ is expressed as
$(1-k)^{2}\cdot f_{s}^{2}$, where $f_{s}$ is the frequency of transition $s$.
The sum of the noise and bias terms defines the total error of $\mathcal{S}$:

(10)
$\mathop{\mathrm{Error}}(\mathcal{S},\epsilon_{2},L_{k})=\sum\nolimits_{s\in\mathcal{S}}[N(s,\epsilon_{2},L_{k})+(1-k)^{2}\cdot
f_{s}^{2}].$

If $k$ is large, more transition information would be reported, which can
effectively reduce the bias error. However, the budget of each transition will
be small, which results in large noise for estimated frequency and hence more
noise error. On the other hand, if $k$ is small, many useful transition states
are omitted, leading to insufficiency to capture the global moving patterns
from crowds. Therefore, the optimal $k$ is chosen to optimize the total error
of $\mathcal{S}$:

(11) $k^{*}=\mathop{\mathrm{argmin}}\nolimits_{0<k\leq
1}~{}\mathop{\mathrm{Error}}(\mathcal{S},\epsilon_{2},L_{k}).$

However, due to the unavailability of true frequency of transitions in the
local setting, it is impossible to directly derive the optimal $k$. We analyze
the impact of $k$ on utility in Section 6.5.3.

Discussion. In $\mathsf{LDPTrace}$, we model the intra-trajectory moving
patterns with the first-order Markov chain (_aka._ transition states), while
we can naturally apply a higher-order Markov chain. However, since the size of
Markov chain grows quickly _w.r.t._ the order, the noise introduced by the
randomness mechanism in LDP can drown out the real signal due to the limited
budget. Empirical results in Section 6.3 show that the first-order Markov
chain is sufficient to model the intra-mobility, and generates authentic
trajectories.

###  5.5. Beginning/Terminated Transitions

Real-world trajectory databases often consist of various trips, such as taxi
trips, home-work commutes, _etc._ These trips usually exhibit special start
point and end point, which reveal the important spatial semantic of
trajectories: pickups, home/work places, destinations, _etc._ Besides, the
start/end points are also useful to guide the random walk during synthesis.
Although we have a mobility model $\mathcal{S}$ for intra-trajectory movement,
we still need a start state and an end state to specify the two endpoints of
generated trajectory. We can naively assume a uniform distribution to randomly
choose a cell from $C$ as a start point to perform random walk and to
terminate the synthesis process when the trajectory reaches the assigned
length, but it contradicts with a well-known fact that the distribution of
start/end points of real trajectories is often heavily skewed (Gursoy et al.,
2018b). For example, many trips might start from or end at homes, while
residential areas are not uniformly distributed in a city. Thus, naive
solution mentioned above, even though simple, will incur bogus synthetic
trajectories that jeopardize utility and authenticity.

To model the distribution of start/end points in trajectories, we add two
special cells, namely, virtual start point $C_{a}$ and virtual end point
$C_{b}$, which are connected to all the geographic cells in $\mathcal{C}$.
$C_{a}$/$C_{b}$ serves as start/end point of any trajectories $T$ to record
$T$’s beginning/terminated state. To be more specific, the beginning
transition state $A_{i}$ denotes that trajectory $T$ begins with $C_{i}$ (from
virtual point $C_{a}$ to cell $C_{i}$), and the terminated transition state
$B_{j}$ means that trajectory $T$ stops with $C_{j}$ (from $C_{j}$ to virtual
end point $C_{b}$). On the user side, we also utilize the OUE protocol to
report a noisy version of the beginning/terminated transition states with
budget $\epsilon_{3}$ on the user side, which is separated from the intra-
trajectory transitions during reporting to reduce their noise since they only
occur once per trajectory (② in Figure 1). On the data curator side, we
combine the intra-transitions with beginning/terminated transitions to form
the aggregated mobility model $\mathcal{M}$ (⑤ in Figure 1). Specifically, the
transition probability from $C_{i}$ to $C_{j}$ can be calculated as:

(12)
$Pr(M_{ij})=\frac{\tilde{g}(M_{ij})}{\sum\nolimits_{r\in\mathcal{N}^{*}_{C_{i}}}\tilde{g}(M_{ir})},$

where $M_{ij}$ represents the transition state from $C_{i}$ to $C_{j}$. If
$C_{i}$ is the virtual start point $C_{a}$, then $M_{ij}=A_{j}$; if $C_{j}$ is
the virtual end point $C_{b}$, then $M_{ij}=B_{i}$; otherwise $M_{ij}=s_{ij}$.
The aggregated neighbor $\mathcal{N}^{*}$ is defined as follows:

(13)
$\mathcal{N}^{*}_{C_{i}}=\begin{cases}\mathcal{N}_{C_{i}}\cup\\{C_{b}\\},&\text{if
}C_{i}\in\mathcal{C}\\\ \mathcal{C},&\text{otherwise }(\emph{i.e.,
}C_{i}\in\\{C_{a},C_{b}\\}).\end{cases}$

Hence, the intra-transitions and the beginning/terminated transitions are
seamlessly integrated into the aggregated mobility model $\mathcal{M}$, which
can denote the overall moving patterns of trajectories.

###  5.6. Trajectory Synthesis

$\mathsf{LDPTrace}$ builds a probabilistic model for private synopsis, which
consists of length distribution $\mathcal{L}$ and aggregated mobility model
$\mathcal{M}$. Accordingly, the synthesis algorithm can be described in three
steps, as depicted in Algorithm 1. First, it determines the length $L$ of
trajectory by sampling from the length distribution $\mathcal{L}$ (line 1).
Second, it initializes $T_{syn}$ by assigning its starting point to the cell
sampled from $\mathcal{N}_{C_{a}}^{*}$ with probability proportional to
$\mathcal{M}$ (lines 2-3). Third, it extends $T_{syn}$ by including a new cell
$C_{next}$ based on its current location. It repeats the extension process
until $C_{next}$ is the virtual end point $C_{b}$ or the length of $T_{syn}$
reaches $L$, whichever is earlier (lines 4-10). Although the above synthesis
scheme makes full use of the estimated patterns, a notable weakness is that
the generated trajectory $T_{syn}$ might be much shorter than $L$ if it
reaches $C_{b}$ in the early part of its extension. Since the distribution of
trajectory terminated points is heavily skewed (_i.e.,_ some points are more
likely to be the destination than others), directly sampling the end point
according to the transition probability would lead to the inauthenticity and
uninformativeness of synthetic trajectories. Thus, we re-weight the terminated
probability $Pr(M_{ib})$ by taking the current length $l$ into consideration:

(14) $\tilde{Pr}(M_{ib})=(\alpha+\beta l)\times Pr(M_{ib}),$

where $\tilde{Pr}(M_{ib})$ is the adjusted termination probability from
current location $C_{i}$ to virtual end point $C_{b}$, and $\alpha$ and
$\beta$ are two hyperparameters to control the influence of length, _i.e.,_
large $\alpha$ and $\beta$ implies that the synthesis process tends to be
stopped even when the length is small, and small $\alpha$ and $\beta$ allows
the model to synthesize trajectories with more points. The final adaptive
synthesis algorithm is presented in Algorithm 1.

To obtain an authentic trajectory database with good utilities, we run the
synthesis algorithm multiple times until the number of synthetic trajectories
reaches the number of trajectories in $\mathcal{T}$. Then, this set of
trajectories $\mathcal{T}_{syn}=\cup T_{syn}$ becomes the substitution of the
real trajectory set $\mathcal{T}$ for various spatial analysis tasks without
sacrificing users’ privacy.

Input: a grid $\mathcal{C}$, a length distribution $\mathcal{L}$, an
aggregated mobility model $\mathcal{M}$, virtual start point/end point
$C_{a}$/$C_{b}$

Output: a candidate synthetic trajectory $T_{\text{syn}}$

1

2trajectory length $L\leftarrow$ sample($\mathcal{L}$)

3 sample $C_{start}\leftarrow$ from $\mathcal{N}^{*}_{C_{a}}$ with probability
proportional to $\mathcal{M}$

4 initialize $T_{syn}$: $T_{syn}[1]\leftarrow C_{start}$

5 for  _$l\leftarrow 2$ to $L$_ do

6 reweight the terminated condition according to Equation (14)

7 sample $C_{next}$ from $\mathcal{N}^{*}_{T_{syn}[l-1]}$ with probability
proportional to $\mathcal{M}$

8 if  _$C_{next}=C_{b}$_ then

9 return $T_{syn}$

10

11 else

12 set $T_{syn}[l]\leftarrow C_{next}$

13

return $T_{syn}$

Algorithm 1 Trajectory synthesis

###  5.7. Privacy Analysis

We now analyze the privacy of the synthesis solution through a sketch proof,
and discuss the budget allocation strategy.

###### Theorem 5.1.

The while process of $\mathsf{LDPTrace}$ satisfies $\epsilon$-LDP.

###### Proof of Theorem 5.1.

$\mathsf{LDPTrace}$ treats $\epsilon$ as the total privacy budget, and
distributes it to three sub-budgets (one for each key feature in the synopsis)
such that $\sum_{i=1}^{3}\epsilon_{i}=\epsilon$. Perturbing and reporting a
feature (length, intra-transition, and start/end transition) consumes the
$\epsilon_{i}$ allocated to it, and thus, depleting the total $\epsilon$ after
the reporting phase is complete, based on the sequential composition property.
Besides, during the intra-mobility modelling, we divide the budget
$\epsilon_{2}$ for each transition state of trajectory, which also satisfies
the sequential composition property. Then, any additional data-independent
operations like aggregation and sampling on the perturbed statistics are
viewed as post-processing. As a result, $\mathsf{LDPTrace}$ remains
$\epsilon$-locally differentially private. ∎

The budget allocation of $\epsilon$ can be configured by $\mathsf{LDPTrace}$
automatically or according to the demands of real applications. The current
implementation of $\mathsf{LDPTrace}$ comes with a default budget
distribution, which was empirically determined to yield high average utility:
$\epsilon_{1}=\epsilon/10$ for length distribution,
$\epsilon_{2}+\epsilon_{3}=9\epsilon/10$ for transitions, where we allocate
equal budget to each transition (_i.e.,_ intra-transitions and
beginning/terminated transitions). We find that the estimation of length
distribution only requires a small budget, while the transitions of
trajectories consume the major budget since they determine the synthesis
process. Although the above strategy is beneficial from the overall utility
maximization perspective, the budget allocation is very flexible, and it can
be easily assigned based on the specific needs of various applications
(_e.g.,_ pick-up identification may need more budget for beginning/terminated
transition estimation).

###  5.8. Computational Cost

We also discuss the computational cost of the proposed $\mathsf{LDPTrace}$,
which highlights how it is far more practical than other alternatives. We
analyze the computational cost from both user side and data curator side in
the following.

Computation on users. We assume that each user keeps one trajectory of his/her
own. Since each perturbation is done locally on individual device, we only
analyze the computational cost for each user/trajectory. First, the cost of
perturbing a binary vector of length is $\mathcal{O}(|\mathcal{C}|)$, where
$|\mathcal{C}|$ is the number of grids. Second, the computational complexity
of intra-transition modelling is $\mathcal{O}(|T||\mathcal{C}|)$, where $|T|$
is the trajectory length. Finally, the cost of adding noise to the
beginning/terminated transitions is also $\mathcal{O}(|\mathcal{C}|)$. Thus,
the overall computation on the user side is $\mathcal{O}(|T||\mathcal{C}|)$.
As all the perturbation can be implemented with bit operations, the
computation is almost negligible and also affordable for any location-aware
devices.

Computation on data curator. After collecting all the perturbed information
from users, data curator first estimates the unbiased frequency with OUE, and
calculates the quantile of length, at the cost of
$\mathcal{O}(|\mathcal{T}||\mathcal{C}|)$, where $|\mathcal{T}|$ is the number
of trajectories/users. Besides, the computational complexity of pattern
estimations (_i.e.,_ length distribution, mobility patterns, and
beginning/terminated states) is $\mathcal{O}(|\mathcal{C}|)$. Moreover, the
synthesis algorithm would cost $\mathcal{O}(|\mathcal{T}|L)$ to synthesize the
same number of trajectories as real trajectories $\mathcal{T}$, where $L$
denotes the mean of length distribution $\mathcal{L}$. Empirical experiments
in Section 6.4 suggest that the synthesis process dominates the running time
of $\mathsf{LDPTrace}$, and $\mathsf{LDPTrace}$ significantly outperforms the
competitor by more than two orders of magnitude. Moreover, the data curator
typically has much more computing power than the mobile devices typically used
by end-users, indicating that $\mathsf{LDPTrace}$ is more flexible than
locally point-based privacy mechanisms (_i.e.,_ $\mathsf{NGRAM}$).

###  5.9. Selecting the Grid Granularity $N$

Finally, we propose a guideline for selecting proper grid granularity $N$ in
the local setting. As mentioned before, grid granularity $N$ is an important
hyperparameter for trajectory representation. We follow (Qardaji et al., 2013)
and analyze the effect of $N$ by considering the range query on trajectories,
which is the most common spatial task used by various real-world applications.
The task of a range query is to retrieve all locations of trajectories that
fall within the query region. Given a rectangular shape query region, let $r$
be the portion of the entire space covered by the query region. There are
mainly two sources of errors in $\mathsf{LDPTrace}$ when performing a range
query. The first is estimation error. In our framework, noise is added to each
transition locally, and the error of estimated transition probability is in
the order of $\sqrt{ne^{\epsilon}/(e^{\epsilon}-1)^{2}}$. Since the query
covers about $rN^{2}$ cells, the total error introduced by perturbation in
this query is in the order of $N\sqrt{nre^{\epsilon}/(e^{\epsilon}-1)^{2}}$.
The second is non-uniformity error that is proportional to the number of data
points in the trajectories that fall on the boundary of the query region
(Qardaji et al., 2013). For a query region that covers $r$ portion of the
entire space (_i.e.,_ grid), the length of each side is proportional to
$\sqrt{r}$ of the domain length, and thus, the number of cells overlapped with
the query’s boundary is in the order of $N\sqrt{r}$, and the total number of
points fallen on the boundary is in the order of $N_{p}/N^{2}\times
N\sqrt{r}=\sqrt{r}N_{p}/{N}$, where $N_{p}$ represents the total number of
points in all synthetic trajectories. The goal is to minimize the sum of two
errors:

(15)
$\mathrm{minimize}~{}N\sqrt{\frac{nre^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{2}}}+\frac{\sqrt{r}N_{p}}{N},$

where $\epsilon^{\prime}=\epsilon_{2}/L$ is the budget for each transition.
Since we cannot obtain trajectory length $L$ before descretization, we replace
it with the geographic distance, which is on the order of $L_{\mathbb{R}}/f$,
where $L_{\mathbb{R}}$ is the average number of points in trajectory, and $f$
is the sampling ratio of the device. Besides, we also use the number of points
on real trajectories $|\mathcal{T}|L_{\mathbb{R}}$ to approximate $N_{p}$.
Finally, by minimizing Equation (15), $N$ should be set as follows:

(16) $N=\lambda\cdot\sqrt[4]{\frac{|\mathcal{T}|L_{\mathbb{R}}(e^{\epsilon
f/L_{\mathbb{R}}}-1)^{2}}{e^{\epsilon f/L_{\mathbb{R}}}}},$

where $\lambda$ is the hyperparameter which depends on the uniformity of the
points distribution in the dataset. Note that all the parameters are easily
obtained from the statistics of trajectory data (such as sampling ratio,
average point count, and the data size), and we also evaluate the
effectiveness of this guideline in Section 6.5.2.

##  6\. Experimental evaluation

In this section, we first introduce the detailed experimental setup. Next, we
conduct experiments on utility as well as efficiency to illustrate the
superiority of $\mathsf{LDPTrace}$. Then, we conduct insight studies to
evaluate the impact of each component in $\mathsf{LDPTrace}$. Finally, we
evaluate the scalability of $\mathsf{LDPTrace}$ and its attack-resilient
ability to various real-word location-based attacks.

###  6.1. Experimental Setup

####  6.1.1. Datasets

We conduct our experiments on four benchmark trajectory datasets. Table 2
summarizes the overall statistics.

  * •

Oldenburg111http://iapg.jade-hs.de/personen/brinkhoff/generator/ is a
synthetic dataset simulated by Brinkhoff’s network-based moving objects
generator. We generate 500,000 trajectories based on the map of Oldenburg
city.

  * •

Porto222http://www.geolink.pt/ecmlpkdd2015-challenge/dataset.html contains
taxi traces over 8 months in the city of Porto. We extract 361,591
trajectories from the central areas.

  * •

Hangzhou is a private trajectory database which consists of the trace of taxis
in Hangzhou city.

  * •

Campus333https://github.com/UBCGeodata/ubc-geospatial-opendata contains 434
buildings of British Columbia campus. We follow (Cunningham et al., 2021b) to
generate 1 million trajectories based on the campus buildings.

####  6.1.2. Baseline

We compare our method with $\mathsf{NGRAM}$ (Cunningham et al., 2021b), which
is the state-of-the-art (and the only) private trajectory publication method
that satisfies rigorous LDP. Different from our approach, $\mathsf{NGRAM}$ is
a point-based perturbation model which directly resembles user’s trajectory in
the local setting. For fair comparison, we discard the auxiliary temporal and
POI information, and only leverage physical distance to ensure the closeness
between original and sampled n-grams in geospatial space.

Table 2. Statistics of the datasets used in our experiments.

Dataset | Size | Average Length | Sampling Interval
---|---|---|---
Oldenburg | 500,000 | 69.75 |  15.6 sec
Porto | 361,591 | 34.13 |  15 sec
Hangzhou | 348,144 | 125.02 |  5 sec
Campus | 1,000,000 | 35.98 |  25 sec

####  6.1.3. Experimental Settings

Based on the guideline described in Section 5.9, the grid granularity
parameter $N$ is set to 6 for Oldenburg, Porto, and Campus dataset, and 8 for
Hangzhou dataset. As for the $k$ quantile of estimated length distribution, we
set it to 0.9 for all the experiments. We generate synthetic database
$\mathcal{T}_{syn}$ with cardinality $|\mathcal{T}_{syn}|=|\mathcal{T}|$ for
utility comparison. We set $\alpha=0.3$ and $\beta=0.2$ for the reweighting
function defined in Equation (14). We set $\lambda=2.5$ for selecting the grid
granularity. As for the query region, we set $r$ as the $1/9$ proportion of
the entire space. Our experiments are conducted on a computer with Intel Xeon
2.1GHz CPU and 32 GB main memory.

Table 3. Utility performance comparison. The best result in each category is
shown in bold. For Kendall-tau and FP F1 Similarity, higher values are better.
For remaining metrics, lower values are better.

| Oldenburg | Porto | Hangzhou | Campus
---|---|---|---|---
| $\epsilon=0.5$ | $\epsilon=1.0$ | $\epsilon=1.5$ | $\epsilon=0.5$ | $\epsilon=1.0$ | $\epsilon=1.5$ | $\epsilon=0.5$ | $\epsilon=1.0$ | $\epsilon=1.5$ | $\epsilon=0.5$ | $\epsilon=1.0$ | $\epsilon=1.5$
Density Error | $\mathsf{NGRAM}$ | 0.0323 | 0.0301 | 0.0274 | 0.3311 | 0.3218 | 0.3049 | 0.1930 | 0.1847 | 0.1831 | 0.1184 | 0.1172 | 0.1105
$\mathsf{LDPTrace}$ | 0.0094 | 0.0077 | 0.0085 | 0.0090 | 0.0081 | 0.0069 | 0.0210 | 0.0194 | 0.0193 | 0.0042 | 0.0043 | 0.0037
Query Error | $\mathsf{NGRAM}$ | 0.3362 | 0.3321 | 0.3206 | 0.8171 | 0.8102 | 0.8055 | 0.6454 | 0.6411 | 0.6332 | 0.7605 | 0.7579 | 0.7611
$\mathsf{LDPTrace}$ | 0.2691 | 0.2595 | 0.2522 | 0.3520 | 0.3312 | 0.3011 | 0.2933 | 0.2814 | 0.2792 | 0.2014 | 0.2011 | 0.1980
Hotspot Query Error | $\mathsf{NGRAM}$ | 0.2972 | 0.2972 | 0.2972 | 1.0000 | 1.0000 | 1.0000 | 0.1529 | 0.1529 | 0.1529 | 0.7001 | 0.7001 | 0.7001
$\mathsf{LDPTrace}$ | 0.0593 | 0.0593 | 0.0530 | 0.0000 | 0.0000 | 0.0000 | 0.0131 | 0.0131 | 0.0131 | 0.0013 | 0.0013 | 0.0000
Kendall-tau | $\mathsf{NGRAM}$ | 0.7479 | 0.7512 | 0.7498 | 0.5442 | 0.5791 | 0.5934 | 0.6164 | 0.6242 | 0.6623 | 0.3794 | 0.3841 | 0.3852
$\mathsf{LDPTrace}$ | 0.8874 | 0.8944 | 0.8942 | 0.6672 | 0.7114 | 0.7581 | 0.6782 | 0.7044 | 0.7174 | 0.8603 | 0.8574 | 0.8667
Trip Error | $\mathsf{NGRAM}$ | 0.1251 | 0.1231 | 0.1230 | 0.5122 | 0.5043 | 0.4979 | 0.4493 | 0.4490 | 0.4421 | 0.3052 | 0.3024 | 0.2995
$\mathsf{LDPTrace}$ | 0.0697 | 0.0683 | 0.0672 | 0.0762 | 0.0778 | 0.0771 | 0.0531 | 0.0513 | 0.0504 | 0.0744 | 0.0740 | 0.0729
Length Error | $\mathsf{NGRAM}$ | 0.1142 | 0.1134 | 0.1112 | 0.1812 | 0.1823 | 0.1791 | 0.02922 | 0.02736 | 0.02607 | 0.1102 | 0.1041 | 0.1045
$\mathsf{LDPTrace}$ | 0.0373 | 0.0370 | 0.0379 | 0.0410 | 0.0399 | 0.0392 | 0.0036 | 0.0037 | 0.0032 | 0.0984 | 0.0981 | 0.0987
Diameter Error | $\mathsf{NGRAM}$ | 0.1244 | 0.1242 | 0.1221 | 0.2201 | 0.2180 | 0.2174 | 0.2013 | 0.1989 | 0.1972 | 0.0682 | 0.0663 | 0.0658
$\mathsf{LDPTrace}$ | 0.0568 | 0.0570 | 0.0562 | 0.0354 | 0.0340 | 0.0331 | 0.0572 | 0.0569 | 0.0563 | 0.0591 | 0.0589 | 0.0587
Pattern F1 | $\mathsf{NGRAM}$ | 0.33 | 0.33 | 0.34 | 0.19 | 0.18 | 0.19 | 0.24 | 0.26 | 0.26 | 0.32 | 0.32 | 0.33
$\mathsf{LDPTrace}$ | 0.69 | 0.69 | 0.69 | 0.67 | 0.63 | 0.65 | 0.80 | 0.80 | 0.80 | 0.71 | 0.71 | 0.72
Pattern Error | $\mathsf{NGRAM}$ | 0.8033 | 0.8004 | 0.7982 | 0.9206 | 0.9232 | 0.9181 | 0.8782 | 0.8725 | 0.8754 | 0.7992 | 0.7912 | 0.7789
$\mathsf{LDPTrace}$ | 0.5693 | 0.5632 | 0.5594 | 0.6498 | 0.6687 | 0.6692 | 0.4593 | 0.4552 | 0.4554 | 0.5502 | 0.5508 | 0.5501

###  6.2. Utility Metrics

To comprehensively quantify the utility of the synthetic trajectories, we
adopt various utility metrics from three categories, including global level,
trajectory level, and semantic level.

Global level utility measures the spatial patterns of trajectories in a global
view, which serves as a building block of various spatial applications like
range query and traffic forecasting. We use the following metrics for
evaluation:

  * •

Density error evaluates the density difference between synthetic trajectory
set $\mathcal{T}_{syn}$ and real trajectory set $\mathcal{T}$.

(17) $Density\
Error=JSD\big{(}\mathcal{D}(\mathcal{T}),\mathcal{D}(\mathcal{T}_{syn})\big{)},$

where $\mathcal{D}(\mathcal{P})$ denotes the grid density distribution in a
given set $\mathcal{P}$, and $JSD(\cdot)$ represents the Jenson-Shannon
divergence between two distributions.

  * •

Query error is a popular measure for evaluating data synthesis algorithms
ranging from tabular data to graph and location data (Chen et al., 2012a,
2014; Li et al., 2014). We consider range queries of trajectories in a random
spatial region $R$, _i.e.,_ $Q(\mathcal{P})$ returns the number of points in
any trajectory of a specified set $\mathcal{P}$ that are within the spatial
region $R$.

(18) $Query\
Error=\frac{|Q(\mathcal{T})-Q(\mathcal{T}_{syn})|}{max\\{Q(\mathcal{T}),z)\\}},$

where $z$ is the sanity bound to weaken the influence of queries that return
very small counts. We set the sanity bound $z$ to
$\frac{\sum_{\mathcal{T}}|T|}{100}$, and report the average result of 200
random queries.

  * •

Hotspot query error measures the ability of preserving spatial hotspots.
Specifically, we choose top-$n_{h}$ mostly visited cells in $\mathcal{T}$ and
$\mathcal{T}_{syn}$ as the hotspots set $H$ and $H_{syn}$, respectively.

(19) $HQE=1-\frac{\sum_{C_{i}\in
H_{syn}}rel(C_{i})/\log(rank_{H_{syn}}(C_{i})+1)}{\sum_{j=1}^{n_{h}}1/(j\cdot\log(j+1))},$

where $rank_{H_{syn}}(C_{i})$ is the position of $C_{i}$ in $H_{syn}$,
$rel(C_{i})$ is the relativity score of $C_{i}$: when $C_{i}\in H$,
$rel(C_{i})=1/rank_{H}(C_{i})$, else $rel(C_{i})=0$. We set $n_{h}=5$.

  * •

Kendall’s tau coefficient is for modelling the discrepancies in locations’
popularity ranking (Gursoy et al., 2018b). Let $\mathcal{D}(C_{i})$ be the
density of cell $C_{i}$, and $(C_{i},C_{j})$ be a concordant pair if and only
if $\mathcal{D}(C_{i})\geq\mathcal{D}(C_{j})$ or
$\mathcal{D}(C_{i})\leq\mathcal{D}(C_{j})$ holds both on $\mathcal{T}$ and
$\mathcal{T}_{syn}$. Otherwise, it’s a discordant pair.

(20)
$Kendall\text{-}tau=\frac{N_{c}-N_{d}}{|\mathcal{C}|(|\mathcal{C}|-1)/2},$

where $N_{c}$ and $N_{d}$ represent the number of concordant pairs and the
number of discordant pairs respectively, and $|\mathcal{C}|$ captures the
total number of grid cells.

Trajectory level utility denotes the spatial features within each trajectory,
which also fascinates a wild range of applications like origin-destination
analysis and commutes studies. We employ the following three evaluation
metrics:

  * •

Trip error measures how well the correlations between trips’ starting points
and ending points are preserved (Gursoy et al., 2018b). Specifically, we
calculate the probability distribution of start/end points in $\mathcal{T}$
and that in $\mathcal{T}_{syn}$, and utilize Jensen-Shannon divergence to
measure their difference.

  * •

Length error focuses on the difference between real and synthetic datasets in
terms of trajectory lengths (_i.e.,_ distance travelled by each trajectory),
which calculates the total distance in a trajectory by adding up the Euclidean
distance between consecutive points.

  * •

Diameter error is defined as the difference of maximum distance frequency
between real and synthetic datasets, where the maximum distance refers to the
maximum Euclidean distance between two points in a trajectory (He et al.,
2015; Jin et al., 2022b).

Since travel distance and diameter are continuous, we follow (Gursoy et al.,
2018b) to separate them into 20 equi-width buckets, and calculate the
distribution of the obtained histogram. We then use Jenson-Shannon divergence
to quantify the above errors.

Table 4. Average runtime in seconds. We report the average running time per
1,000 trajectories of each component.

|  $\mathsf{LDPTrace}$: User side |  $\mathsf{LDPTrace}$: Curator side | Total | $\mathsf{NGRAM}$ Total
---|---|---|---|---
| Length | Intra-traj tran. | Beg./Ter. tran. | Preparation | Pattern est. | Synthesis
Oldenburg | 0.030 | 0.192 | 0.104 | 0.010 | 0.001 | 0.219 | 0.556 | 183
Porto | 0.028 | 0.148 | 0.092 | 0.015 | 0.001 | 0.179 | 0.463 | 132
Hangzhou | 0.028 | 0.302 | 0.098 | 0.012 | 0.002 | 0.304 | 0.746 | 418
Campus | 0.028 | 0.138 | 0.083 | 0.009 | 0.001 | 0.189 | 0.448 | 197

Semantic level metrics. Apart from the aforementioned statistic metrics of
trajectories’ attributes, we also adopt two semantic level metrics to mine the
mobility patterns that are hidden behind those statistics. A pattern $P$ is
defined as an ordered sequence of consecutive cells, and we select top-$n$
most occurred patterns in $\mathcal{T}$ and $\mathcal{T}_{syn}$, denoted as
pattern sets $FP$ and $FP_{syn}$ respectively, and calculate the following
metrics:

  * •

Pattern F1 evaluates the similarity between the selected most frequent pattern
sets $FP$ and $FP_{syn}$:

(21) $Pattern\ F1=2\times\frac{Precision(FP,FP_{syn})\times
Recall(FP,FP_{syn})}{Precision(FP,FP_{syn})+Recall(FP,FP_{syn})}.$

  * •

Pattern Error measures the relative difference between the number of pattern
occurrences in each dataset:

(22) $Pattern\ Error=\frac{1}{|FP|}\textstyle\sum_{P\in
FP}\frac{|n^{P}-n^{P}_{syn}|}{n^{P}},$

where $n^{P}$/$n^{P}_{syn}$ is the number of occurrence of pattern $P$ in the
dataset $FP$/$FP_{syn}$, and we use top 100 frequent patterns (_i.e.,_
$|FP|=100$) for evaluation.

Table 5. Impact of beginning/terminated transitions. Best result is shown in
bold. HQ Error denotes “Hotpot Query Error”.

Dataset | Model | Density Error | Query Error | HQ Error | Kendall-tau | Trip Error | Length Error | Diameter Error | Pattern F1 | Pattern Error
---|---|---|---|---|---|---|---|---|---|---
Oldenburg | $\mathsf{RandSyn}$ | 0.0569 | 0.7491 | 0.0724 | 0.6623 | 0.1779 | 0.0694 | 0.0611 | 0.58 | 0.4313
$\mathsf{CombTran}$ | 0.0168 | 0.2794 | 0.0593 | 0.8108 | 0.1052 | 0.0371 | 0.0570 | 0.67 | 0.5596
$\mathsf{NoAdapt}$ | 0.0081 | 0.3754 | 0.0013 | 0.8866 | 0.0971 | 0.0713 | 0.0932 | 0.69 | 0.6822
$\mathsf{LDPTrace}$ | 0.0077 | 0.2595 | 0.0593 | 0.8944 | 0.0683 | 0.0370 | 0.0570 | 0.69 | 0.5632
Porto | $\mathsf{RandSyn}$ | 0.2687 | 7.4933 | 0.2583 | 0.2191 | 0.4372 | 0.1244 | 0.1460 | 0.39 | 0.6658
$\mathsf{CombTran}$ | 0.0243 | 0.6741 | 0.0464 | 0.5784 | 0.0932 | 0.0412 | 0.0351 | 0.59 | 0.6730
$\mathsf{NoAdapt}$ | 0.0098 | 0.3607 | 0.0464 | 0.6828 | 0.1052 | 0.0579 | 0.0631 | 0.63 | 0.7674
$\mathsf{LDPTrace}$ | 0.0081 | 0.3312 | 0.0000 | 0.7114 | 0.0778 | 0.0399 | 0.0340 | 0.63 | 0.6687
Hangzhou | $\mathsf{RandSyn}$ | 0.1928 | 2.4842 | 0.0144 | 0.5252 | 0.4471 | 0.0549 | 0.1344 | 0.49 | 0.3821
$\mathsf{CombTran}$ | 0.0361 | 0.3426 | 0.0464 | 0.6492 | 0.0762 | 0.0040 | 0.0594 | 0.78 | 0.4890
$\mathsf{NoAdapt}$ | 0.0322 | 0.3641 | 0.0131 | 0.7062 | 0.0593 | 0.0041 | 0.0921 | 0.80 | 0.5866
$\mathsf{LDPTrace}$ | 0.0194 | 0.2814 | 0.0131 | 0.7044 | 0.0513 | 0.0037 | 0.0569 | 0.80 | 0.4552
Campus | $\mathsf{RandSyn}$ | 0.0914 | 1.5203 | 0.3055 | 0.5587 | 0.2811 | 0.0982 | 0.0589 | 0.64 | 0.4109
$\mathsf{CombTran}$ | 0.0103 | 0.3025 | 0.0304 | 0.8539 | 0.0862 | 0.0973 | 0.0593 | 0.71 | 0.5780
$\mathsf{NoAdapt}$ | 0.0046 | 0.3766 | 0.0593 | 0.8571 | 0.0502 | 0.1496 | 0.0590 | 0.71 | 0.6892
$\mathsf{LDPTrace}$ | 0.0043 | 0.2011 | 0.0013 | 0.8571 | 0.0740 | 0.0981 | 0.0587 | 0.71 | 0.5508

###  6.3. Utility Evaluation

In our first set of experiments, we compare the utility performance of
$\mathsf{LDPTrace}$ and $\mathsf{NGRAM}$ with various privacy budgets
$\epsilon$. For each experiment, we perform the synthesis 5 times, and report
the average results in Table 3. Generally speaking, $\mathsf{LDPTrace}$
outperforms $\mathsf{NGRAM}$ in all utility metrics across all datasets, which
well demonstrates the robustness and strong utility-preserving ability of
$\mathsf{LDPTrace}$. Based on the in-depth analysis of the results, we have
made the following detailed observations.

  * •

We first analyze the performance _w.r.t._ different types of utility metrics.
Since $\mathsf{NGRAM}$ fails to take the global features of trajectories into
consideration, it suffers from severe performance degradation on the global
level utility. Especially, the density error in $\mathsf{LDPTrace}$ is _three
times_ smaller than that in $\mathsf{NGRAM}$, which implies that the
trajectories generated by $\mathsf{NGRAM}$ fail to preserve the geospatial
density due to the point-based perturbation. Also, our method shows strong
performance in both the trajectory level and the semantic level utilities. We
contribute the improvement to the mobility modelling and adaptive synthesis of
$\mathsf{LDPTrace}$: (1) By collecting transitions from both intra-trajectory
and start/end points, $\mathsf{LDPTrace}$ is able to synthesize trajectories
whose mobility patterns (_e.g.,_ moving directions) assemble users’ real
traces. In contrast, $\mathsf{NGRAM}$ aims to preserve the local $n$-gram
closeness when perturbing, but ignores the critical sequential features of
trajectories in a global view. (2) Benefited from the adaptive synthesis
algorithm, $\mathsf{LDPTrace}$ can generate authentic trajectories with proper
length to maintain the relationship between start points and end points, while
the point-based $\mathsf{NGRAM}$ fails to capture the long-term dependence
between beginning and terminated transitions.

  * •

Next, we evaluate the effectiveness _w.r.t._ different datasets. We find that
the performance of our framework is robust, which keeps good utility on both
synthetic and real-world datasets. However, the performance of
$\mathsf{NGRAM}$ varies across datasets. Specifically, it achieves competitive
results in terms of density error and trip error on Oldenburg, but the results
of these metrics are much worse in the two real datasets. We argue that this
is because the mobility patterns of real-world trajectories are much more
complex than synthetic ones, and $\mathsf{NGRAM}$ is unable to capture these
patterns with n-gram model.

  * •

We also examine the effects _w.r.t._ different privacy budgets $\epsilon$. It
is worth mentioning that $\mathsf{LDPTrace}$ could achieve good performance
even when the budget is small (_e.g.,_ $\epsilon=0.5$), which confirms the
effectiveness of capturing trajectories’ key patterns with only a few
distributions. However, $\mathsf{NGRAM}$ relies on a large budget to achieve
reasonable performance, meaning that it needs to relax the privacy guarantee
for practical use. For privacy budget $\epsilon$, the protection is acceptable
as long as the budget is less than 2 (Erlingsson et al., 2014; Team, 2017;
Wang et al., 2017a; Zeighami et al., 2022). To align with other real-world
deployments of LDP by Google (Erlingsson et al., 2014) and Microsoft (Ding et
al., 2017), we set $\epsilon=1$ in the following experiments.

###  6.4. Efficiency Evaluation

Since efficiency is equally important as utility for real-world deployments,
we conduct comprehensive experiments to evaluate the average running time of
each component, which is detailed in Table 4. Generally speaking,
$\mathsf{LDPTrace}$ is a very efficient privacy-preserving trajectory
publication framework, which is more than _300 times_ faster than
$\mathsf{NGRAM}$. The reason is that $\mathsf{NGRAM}$ suffers from time-
consuming processes like solving linear programming problem and recursive
reconstructions, not to mention the expensive cost of pre-processing for POIs
and other external knowledge, which greatly hinders its use on mobile devices.
We would like to highlight that this observation is consistent with the
authors’ claims in their paper (Cunningham et al., 2021b), as they also report
up to 4 seconds per generated trajectory.

As for the breakdown of time spent on each component, we find that the major
computation at user side is the perturbation of intra-trajectory transitions
because it has to perturb and upload multiple times to report the holistic
transition states. Other one-time operations like trajectory length
perturbation are much faster, consistent with the computational analysis
presented in Section 5.8. On the data curator side, the main computation is
incurred by the synthesis process, since it needs to generate location points
sequentially according to the transition probability. Overall,
$\mathsf{LDPTrace}$ is highly efficient and practical for real-world
applications, and the time cost for privacy protection is nearly imperceptible
for users.

Figure 2. Impact of grid granularity $N$ with optimal $N$ values derived based
on Equation (16) represented by dotted lines.  Figure 3. (a) Impact of
$\lambda$. (b) Impact of query size $r$. (c) Impact of granularity $N$ on
total runtime (seconds).

###  6.5. Analysis of $\mathsf{LDPTrace}$

As the pattern modelling is at the core of $\mathsf{LDPTrace}$, we also
conduct insight experiments to investigate its effectiveness, _i.e.,_ how the
presence of beginning/terminated transitions, grid granularity, and the
adaptive synthesis algorithm affect our model.

####  6.5.1. Impact of beginning/terminated transitions.

We first verify the effectiveness of the beginning/terminated transitions. To
this end, we construct three variants of $\mathsf{LDPTrace}$, including (1)
$\mathsf{RandSyn}$ that discards the virtual start/end points from
$\mathsf{LDPTrace}$, and synthesizes trajectories according to intra-
transition probabilities, (2) $\mathsf{CombTran}$ that combines the
beginning/terminated transitions with intra-transitions, and perturbs/reports
them as a whole, and (3) $\mathsf{NoAdapt}$ that removes the adaptive
synthesis strategy (_i.e.,_ Equation (14)). We summarize the results in Table
5.

Compared with the complete model $\mathsf{LDPTrace}$, the absence of the
beginning/terminated transitions (_i.e.,_ $\mathsf{RandSyn}$) dramatically
degrades the utility, indicating the necessity of modelling the start/end
point distribution. However, it is noticed that the pattern error of
$\mathsf{RandSyn}$ remains small, since it measures the frequent intra-
mobility patterns that are less irrelevant with endpoints. $\mathsf{CombTran}$
introduces unnecessary noise for estimating beginning/terminated transitions
as they will be perturbed along the intra-transitions. Thus, it also results
in some utility loss. Last but not the least, directly synthesizing trajectory
without considering current length will make the synthetic trajectory too
short to represent useful spatial patterns, incurring suboptimal performance.

####  6.5.2. Impact of grid granularity $N$

We analyze the influence of different grid granularity settings to empirically
verify the effectiveness of our guideline for choosing $N$. Specifically, we
utilize the query error metric to measure the impact of grid granularity.
Figure 2 depicts the results, consistent with the analysis presented in
Section 5.9. We can observe that the performance reaches near optimal at the
estimated granularity which is derived from Equation (16), _i.e.,_ 8 for
Hangzhou dataset and 6 for the other three datasets. In addition, we see
similar trend with respect to the performance of $\mathsf{NGRAM}$. The reason
behind is that our estimation only depends on the statistics of trajectory
dataset, which is model-agnostic, and can be a good reference to choose the
grid granularity for all locally private methods.

Figure 4. Scalability evaluation.

Besides, since the granularity will influence the trajectory length and the
number of transition states, we also test the running time of
$\mathsf{LDPTrace}$ under different $N$ values in Figure 3(c). There is a
clear increasing trend of runtime as $N$ increases its value and each grid
becomes more fine-grained. Consequently, a wrong choice of granularity will
not only cause the utility degradation, but also result in larger
computational complexity.

Table 6. Utility performance comparison with unmodified $\mathsf{NGRAM}$ on
Campus dataset.

Model | Density Error | Query Error | HQ Error | Kendall-tau | Trip Error | Length Error | Diameter Error | Pattern F1 | Pattern Error
---|---|---|---|---|---|---|---|---|---
$\mathsf{NGRAM}$ | 0.1172 | 0.7579 | 0.7001 | 0.3841 | 0.3024 | 0.1041 | 0.0663 | 0.32 | 0.7912
unmodified $\mathsf{NGRAM}$ | 0.0536 | 0.4371 | 0.8108 | 0.6349 | 0.2006 | 0.1122 | 0.0638 | 0.55 | 0.8215
$\mathsf{LDPTrace}$ | 0.0043 | 0.2011 | 0.0013 | 0.8571 | 0.0740 | 0.0981 | 0.0587 | 0.71 | 0.5508

Figure 5. Impact of quantile $k$ of length distribution.

####  6.5.3. Impact of quantile $k$

For space reason, we only choose one representative utility metric each from
global, trajectory, and semantic levels (_i.e.,_ query error, diameter error,
and pattern F1) to explore the influence of quantile $k$. In general, the
selection of trajectory length has different impacts on different utilities.
When the quantile $k$ is small, more transitions will be truncated, and a
large bias will be introduced to intra-transition modelling, leading to a
large query error. On the other hand, when $k$ becomes larger, the budget of
each reported transition is smaller, and thus, the added noise increases and
the synthetic trajectories may be unreliable, which results in a larger
diameter error. In conclusion, we choose $k=0.9$, since it achieves a good
trade-off among different utilities.

The choice of $k$ also impacts the efficiency of $\mathsf{LDPTrace}$. As
illustrated in the last subfigure of Figure 5, the running time grows plainly
with the growth of $k$. It is consistent with our expectation because a larger
$k$ requires a longer amount of time for perturbation and reporting. However,
the magnitude of the time increase is insignificant, because our algorithm is
super efficient. Hence, the influence of more perturbations is almost
negligible.

####  6.5.4. Impact of $\lambda$ and query size $r$.

We conduct experiments on different $\lambda$ and query size $r$ to further
analyze the effectiveness of the granularity selection method. Recall that
$\lambda$ is the hyperparameter which depends on the uniformity of the points
distribution in the dataset. As shown in Figure 3(a), we find that
$\lambda=2.5$ achieves good performance across different datasets, since it
reaches good balance between non-uniformity error and transition estimation
error.

As shown in Figure 3(b), the query error increases plainly when the query size
$r$ becomes larger. There are two competing effects when increasing $r$: on
the one hand, the error from more grid cells is aggregated; on the other hand,
each query is less affected by noise, since actual counts are larger. The
first effect is stronger, so the overall error increases with query size. The
results are consistent with prior studies (Zeighami et al., 2022).

###  6.6. Scalability

We also study the scalability of $\mathsf{LDPTrace}$ by varying the
cardinality of the trajectory datasets. We observe similar trends in all four
datasets. Due to space limitation, We only report the total running time under
Porto and Campus datasets in Figure 4. As observed, $\mathsf{LDPTrace}$ is
consistently faster than $\mathsf{NGRAM}$ in all different dataset scales, and
has _two orders of magnitude_ improvement. $\mathsf{LDPTrace}$ also has stable
performance, and the processing time will not grow sharply with the growth of
the dataset size. For $\mathsf{NGRAM}$, it takes more than two days in
processing all the trajectories when the dataset is at the scale of millions,
while $\mathsf{LDPTrace}$ can finish the whole process in less than 10
minutes. Therefore, $\mathsf{LDPTrace}$ is suitable for large-scale deployment
with little computational cost.

###  6.7. Comparison with unmodified $\mathsf{NGRAM}$

To further demonstrate the superiority of $\mathsf{LDPTrace}$, we also compare
it against the unmodified $\mathsf{NGRAM}$ with external knowledge.
Specifically, we use the same Campus dataset described in (Cunningham et al.,
2021b), and carefully attach the auxiliary knowledge (POIs, temporal
information, hierarchical category) to the original trajectories. The results
of unmodified $\mathsf{NGRAM}$ are reported in Table 6. As observed,
$\mathsf{LDPTrace}$ outperforms both $\mathsf{NGRAM}$ and unmodified
$\mathsf{NGRAM}$ for all utility metrics by a large margin. Although
unmodified $\mathsf{NGRAM}$ benefits from the deterministic constraints of
external knowledge to ensure the semantic similarity between original and
perturbed locations, it still fails to capture the moving patterns properly.

Figure 6. Attack resilience analysis on Oldenburg dataset.

###  6.8. Attack Resilience

In our last set of experiments, we investigate $\mathsf{LDPTrace}$’s
resistance to two common attacks, which are defined below.

Re-identification Attack. Suppose the attackers are able to obtain some
spatial locations of a user, _e.g.,_ users can be easily tracked when they
enter some public sensitive zones like train stations and shopping malls. With
this subtrajectory $T_{a}$ _w.r.t._ a specific user $u$ as external knowledge,
the attackers aim to identify the individual $u$ in the published dataset
$\mathcal{T}_{syn}$, and acquire information about the attacked user $u$’s
whole trajectory. The defense goal is to ensure that there are at least
$\kappa$ traces in $\mathcal{T}_{syn}$ having their similarity distances to
$T_{a}$ below a given threshold $\vartheta$, so that the attacker is unable to
identify the true user $u$ even with $u$’s subtrajectory $T_{a}$. Formally,
the re-identification attack is defined below:

###### Definition 0 (Re-Identification Attack).

Let $M_{T_{a}}$ denote the set of trajectories in $\mathcal{T}_{syn}$ that are
similar to a given subtrajectory $T_{a}$, $sim(T,T^{\prime})$ measures the
similarity between two trajectories $T$ and $T^{\prime}$, and $Z$ denote the
selected sensitive zones.

(23) $M_{T_{a}}=\\{T|T\in\mathcal{T}_{syn},sim(T_{a},T\cap
Z)\leq\vartheta\\}.$

If $|M_{a}|>\kappa$, the attack is successfully defensed.

In our experiments, we set $2\times 2$ grids in the central area of the map as
the sensitive zone, use DTW distance as the similarity distance, and set
$\vartheta=0.2\times sim_{max}$, where $sim_{max}$ denotes the maximum DTW
distance of real trajectories in sensitive zones.

Outlier attack. In this scenario, the attackers focus on some records that
have irregular attributes like outliers, which are relatively far from their
neighbors, _e.g.,_ trajectories with extremely long travel distance or unusual
start/end locations that others seldom reach. Hence, it is easier to
distinguish them from other normal trajectories, which may cause privacy
leakage. We follow (Gursoy et al., 2018b), and define this attack as follows:

###### Definition 0 (Outlier Attack).

For any outlier $T_{o}\in\mathcal{T}_{syn}$, let $M_{T_{o}}$ denote the
matching set that includes all the real trajectories in $\mathcal{T}$ that are
similar to $T_{o}$, and similarity function $sim(\cdot)$ measures the travel
distance difference between two trajectories with $\delta=0.25\times
sim_{max}$. If $|M_{T_{o}}|>\kappa$, the attack is successfully defensed.

(24) $M_{T_{o}}=\\{T|T\in\mathcal{T},sim(T_{o},T)\leq\delta\\}$

To measure our model’s defense ability to the aforementioned attacks, we
defineresilience ratio as follows:

(25) $Resilience\ Ratio=\frac{\sum_{T_{a}\in
D_{a}}{\mathbbm{1}(|M_{T_{a}}|>\kappa)}}{|D_{a}|}$

where $D_{a}$ is the set of trajectories to be attacked.

The results on Oldenburg dataset are shown in Figure 6, while the results of
other datasets are omitted due to similar trend and limited space. The results
indicate that $\mathsf{LDPTrace}$ has impressive ability to resist these two
attacks: more than 88% trajectories can be successfully protected in re-
identification attack, and all trajectories are hidden from outliers when the
privacy parameter $\kappa$ changes its value from 2 to 10. On the contrary,
$\mathsf{NGRAM}$ cannot provide provable protections to these attacks,
especially when the demand of protection is more strict (large privacy
parameter $\kappa$). We contribute the superiority of $\mathsf{LDPTrace}$ to
the synthesis design: since the published trajectories are synthesized from
learned patterns, they do not resemble any real trajectory. Thus, it is much
more difficult for attackers to identify traces that they are interested in.

##  7\. Conclusions

In this paper, we develop a neat yet effective trajectory synthesis framework
under the rigorous privacy of LDP, called $\mathsf{LDPTrace}$, which achieves
strong utility and efficiency simultaneously. Besides, $\mathsf{LDPTrace}$ can
provide deterministic resilience against common location-based attacks. We
also provide a theoretical guideline for selecting the grid granularity
without consuming any privacy budgets. Extensive experiments conducted on
three datasets demonstrate the superiority of $\mathsf{LDPTrace}$. In the near
future, we aim to extract more complex patterns from user’s trajectory (like
second-order Markov chain and average speed) to further enhance the
authenticity of synthetic trajectories, and to investigate the LDP-based
synthesis problem on streaming trajectories to empower real-time location-
based applications.

##  Appendix A appendix

###### Theorem A.1 (Mean and Variance of an OUE Ratio).

Given the unbiased frequency estimations of value $x$ and value $y$ (_i.e.,_
$\tilde{g}(x)$ and $\tilde{g}(y)$) with OUE, Equation (26), and Equation (27)
define the approximated mean and variance, respectively.

(26)
${\mathop{\mathrm{E}}}^{*}[\frac{\tilde{g}(x)}{\tilde{g}(y)}]=\frac{f_{x}}{f_{y}},$
(27)
${\mathop{\mathrm{Var}}}^{*}[\frac{\tilde{g}(x)}{\tilde{g}(y)}]=\frac{\left(f_{x}\right)^{2}}{\left(f_{y}\right)^{2}}\left[\frac{\sigma_{x}^{2}}{\left(f_{x}\right)^{2}}-2\frac{\operatorname{Cov}(x,y)}{f_{x}f_{y}}+\frac{\sigma_{y}^{2}}{\left(f_{y}\right)^{2}}\right],$

where $f_{x}$ and $f_{y}$ are the true frequencies of $x$ and $y$,
respectively; $\sigma_{x}^{2}$ and $\sigma_{y}^{2}$ are the variance of OUE
for estimators $\tilde{g}(x)$ and $\tilde{g}(y)$, respectively.

###### Proof of Theorem A.1.

For any function $f(X,Y)$, we can choose the expansion point to be
$\theta=(\mu_{x},\mu_{y})$, and the first order Taylor series approximation
for $f(X,Y)$ is:

$\displaystyle\mathop{\mathrm{E}}[f(X,Y)]$
$\displaystyle\approx\mathop{\mathrm{E}}[f(\theta)]+\mathop{\mathrm{E}}\left[f_{x}^{\prime}({\theta})\left(X-\mu_{x}\right)\right]+\mathop{\mathrm{E}}\left[f_{y}^{\prime}({\theta})\left(Y-\mu_{y}\right)\right]$
$\displaystyle=\mathop{\mathrm{E}}[f(\theta)]+f_{x}^{\prime}({\theta})\mathop{\mathrm{E}}\left[\left(X-\mu_{x}\right)\right]+f_{y}^{\prime}({\theta})\mathop{\mathrm{E}}\left[\left(Y-\mu_{y}\right)\right]$
$\displaystyle=f\left(\mu_{x},\mu_{y}\right).$

Let $f(x,y)=x/y$, and the approximation holds
${\mathop{\mathrm{E}}}^{*}[f(X,Y)]=f(\mu_{x},\mu_{y})=\mu_{x}/\mu_{y}$.
Therefore, the mean of an OUE ratio $\tilde{g}(x)/\tilde{g}(y)$ approximates
$f_{x}/f_{y}$, where $\mathop{\mathrm{E}}[\tilde{g}(x)]=f_{x}$ and
$\mathop{\mathrm{E}}[\tilde{g}(y)]=f_{y}$.

Besides, the variance of $f(X,Y)$ is:

$\displaystyle{\mathop{\mathrm{Var}}}[f(X,Y)]=\mathop{\mathrm{Var}}\left\\{[f(X,Y)-E(f(X,Y))]^{2}\right\\}\approx\mathop{\mathrm{Var}}\left\\{[f(X,Y)-f(\theta)]^{2}\right\\}$

Then using the first order Taylor expansion for $f(X,Y)$ around $\theta$:

$\displaystyle\mathop{\mathrm{Var}}[f(X,Y)]$
$\displaystyle\approx\mathop{\mathrm{E}}\left\\{\left[f(\theta)+f_{x}^{\prime}({\theta})\left(X-\theta_{x}\right)+f_{y}^{\prime}(\theta)\left(Y-\theta_{y}\right)-f(\theta)\right]^{2}\right\\}$
$\displaystyle=f_{x}^{\prime
2}({\theta})\mathop{\mathrm{Var}}(X)+2f_{x}^{\prime}({\theta})f_{y}^{\prime}(\theta)\operatorname{Cov}(X,Y)+f_{y}^{\prime
2}({\theta})\mathop{\mathrm{Var}}(Y)$

where $f(x,y)=x/y$, and the approximated variance is:

$\displaystyle{\mathop{\mathrm{Var}}}^{*}[X/Y]$
$\displaystyle=\frac{\left(\mu_{x}\right)^{2}}{\left(\mu_{y}\right)^{2}}\left[\frac{\sigma_{x}^{2}}{\left(\mu_{x}\right)^{2}}-2\frac{\operatorname{Cov}(X,Y)}{\mu_{x}\mu_{y}}+\frac{\sigma_{y}^{2}}{\left(\mu_{y}\right)^{2}}\right]$

∎

###### Acknowledgements.

This work was supported by the NSFC under Grants No. (62025206, 61972338, and
62102351). Lu Chen is the corresponding author of the work.

## References

  * (1)
  * Acs and Castelluccia (2014) Gergely Acs and Claude Castelluccia. 2014.  A Case Study: Privacy Preserving Release of Spatio-Temporal Density in Paris. In _KDD_. 1679–1688.
  * Andrés et al. (2013) Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013\.  Geo-indistinguishability: Differential privacy for location-based systems. In _CCS_. 901–914.
  * Bassily et al. (2017) Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2017.  Practical Locally Private Heavy Hitters. In _NeurIPS_. 2285–2293.
  * Bindschaedler and Shokri (2016) Vincent Bindschaedler and Reza Shokri. 2016.  Synthesizing Plausible Privacy-Preserving Location Traces. In _IEEE Symposium on Security and Privacy (SP)_. 546–563.
  * Bonomi and Xiong (2013) Luca Bonomi and Li Xiong. 2013.  A two-phase algorithm for mining sequential patterns with differential privacy. In _CIKM_. 269–278.
  * Cai et al. (2021) Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. 2021\.  Data synthesis via differentially private markov random fields. In _VLDB_. 2190–2202.
  * Cao et al. (2017) Yang Cao, Masatoshi Yoshikawa, Yonghui Xiao, and Li Xiong. 2017.  Quantifying Differential Privacy under Temporal Correlations. In _ICDE_. 821–832.
  * Chen et al. (2012a) Rui Chen, Gergely Acs, and Claude Castelluccia. 2012a.  Differentially private sequential data publication via variable-length n-grams. In _CCS_. 638–649.
  * Chen et al. (2012b) Rui Chen, Benjamin CM Fung, Bipin C Desai, and Nériah M Sossou. 2012b.  Differentially private transit data publication: a case study on the montreal transportation system. In _KDD_. 213–221.
  * Chen et al. (2014) Rui Chen, Benjamin C. Fung, Philip S. Yu, and Bipin C. Desai. 2014.  Correlated Network Data Publication via Differential Privacy.  _The VLDB Journal_ 23, 4 (aug 2014), 653–676.
  * Cormode et al. (2018) Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. 2018\.  Privacy at scale: Local differential privacy in practice. In _SIGMOD_. 1655–1658.
  * Cormode et al. (2021) Graham Cormode, Samuel Maddock, and Carsten Maple. 2021\.  Frequency estimation under local differential privacy. In _VLDB_. 2046–2058.
  * Cunningham et al. (2021a) Teddy Cunningham, Graham Cormode, and Hakan Ferhatosmanoglu. 2021a.  Privacy-Preserving Synthetic Location Data in the Real World. In _SSTD_. 23–33.
  * Cunningham et al. (2021b) Teddy Cunningham, Graham Cormode, Hakan Ferhatosmanoglu, and Divesh Srivastava. 2021b.  Real-World Trajectory Sharing with Local Differential Privacy. In _PVLDB_. 2283–2295.
  * Ding et al. (2017) Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017\.  Collecting telemetry data privately. In _NeurIPS_. 3574–3583.
  * Du et al. (2021) Linkang Du, Zhikun Zhang, Shaojie Bai, Changchang Liu, Shouling Ji, Peng Cheng, and Jiming Chen. 2021.  AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy. In _CCS_. 1266–1288.
  * Duchi et al. (2013) John C Duchi, Michael I Jordan, and Martin J Wainwright. 2013\.  Local privacy and statistical minimax rates. In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_. 429–438.
  * Dwork (2006) Cynthia Dwork. 2006\.  Differential Privacy. In _Automata, Languages and Programming_. 1–12.
  * Erlingsson et al. (2014) Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014\.  RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In _CCS_. 1054–1067.
  * Ge et al. (2021) Chang Ge, Shubhankar Mohapatra, Xi He, and Ihab F. Ilyas. 2021\.  Kamino: Constraint-Aware Differentially Private Data Synthesis. In _VLDB_. 1886–1899.
  * Gu et al. (2019) Xiaolan Gu, Ming Li, Yang Cao, and Li Xiong. 2019\.  Supporting both range queries and frequency estimation with local differential privacy. In _2019 IEEE Conference on Communications and Network Security (CNS)_. 124–132.
  * Gursoy et al. (2018a) Mehmet Emre Gursoy, Ling Liu, Stacey Truex, and Lei Yu. 2018a.  Differentially private and utility preserving publication of trajectory data.  _IEEE Transactions on Mobile Computing_ 18, 10 (2018), 2315–2329.
  * Gursoy et al. (2018b) Mehmet Emre Gursoy, Ling Liu, Stacey Truex, Lei Yu, and Wenqi Wei. 2018b.  Utility-Aware Synthesis of Differentially Private and Attack-Resilient Location Traces. In _ACM SIGSAC Conference on Computer and Communications Security_. 196–211.
  * Gursoy et al. (2020) M Emre Gursoy, Vivekanand Rajasekar, and Ling Liu. 2020\.  Utility-Optimized Synthesis of Differentially Private Location Traces. In _2020 Second IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA)_. 30–39.
  * 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. In _PVLDB_. 2150–8097.
  * Jiang et al. (2021) Hongbo Jiang, Jie Li, Ping Zhao, Fanzi Zeng, Zhu Xiao, and Arun Iyengar. 2021\.  Location Privacy-Preserving Mechanisms in Location-Based Services: A Comprehensive Survey.  _ACM Comput. Surv._ 54, 1, Article 4 (2021), 36 pages.
  * Jin et al. (2022a) Fengmei Jin, Wen Hua, Matteo Francia, Pingfu Chao, Maria Orlowska, and Xiaofang Zhou. 2022a.  A survey and experimental study on privacy-preserving trajectory data publishing.  _TKDE_ (2022).
  * Jin et al. (2022b) Fengmei Jin, Wen Hua, Boyu Ruan, and Xiaofang Zhou. 2022b.  Frequency-based Randomization for Guaranteeing Differential Privacy in Spatial Trajectories. In _ICDE_. 1727–1739.
  * Johnson et al. (2018) Noah Johnson, Joseph P Near, and Dawn Song. 2018.  Towards practical differential privacy for SQL queries. In _VLDB_. 526–539.
  * Li et al. (2014) Haoran Li, Li Xiong, and Xiaoqian Jiang. 2014.  Differentially private synthesization of multi-dimensional data using copula functions. In _EDBT_. 475.
  * Li et al. (2012) Ninghui Li, Wahbeh Qardaji, Dong Su, and Jianneng Cao. 2012\.  PrivBasis: Frequent Itemset Mining with Differential Privacy. In _VLDB_. 1340–1351.
  * Li et al. (2013) Ninghui Li, Wahbeh Qardaji, Dong Su, Yi Wu, and Weining Yang. 2013.  Membership Privacy: A Unifying Framework for Privacy Definitions. In _CCS_. 889–900.
  * Li et al. (2020) Zitao Li, Tianhao Wang, Milan Lopuhaä-Zwakenberg, Ninghui Li, and Boris Škoric. 2020.  Estimating numerical distributions under local differential privacy. In _SIGMOD_. 621–635.
  * Montjoye et al. (2013) Yves-Alexandre Montjoye, Cesar Hidalgo, Michel Verleysen, and Vincent Blondel. 2013.  Unique in the Crowd: The Privacy Bounds of Human Mobility.  _Scientific reports_ 3 (03 2013), 1376.
  * Qardaji et al. (2013) Wahbeh Qardaji, Weining Yang, and Ninghui Li. 2013.  Differentially private grids for geospatial data. In _ICDE_. 757–768.
  * Team (2017) Apple Differential Privacy Team. 2017\.  Learning with Privacy at Scale.  https://machinelearning.apple.com/research/learning-with-privacy-at-scale
  * 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 _32th USENIX Security Symposium (USENIX Security 23)_.
  * Wang et al. (2017b) Ning Wang, Xiaokui Xiao, Yin Yang, Zhenjie Zhang, Yu Gu, and Ge Yu. 2017b.  PrivSuper: a superset-first approach to frequent itemset mining under differential privacy. In _ICDE_. 809–820.
  * Wang et al. (2017a) Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017a.  Locally differentially private protocols for frequency estimation. In _26th USENIX Security Symposium (USENIX Security 17)_. 729–745.
  * Wang et al. (2021) Tianhao Wang, Joann Qiongna Chen, Zhikun Zhang, Dong Su, Yueqiang Cheng, Zhou Li, Ninghui Li, and Somesh Jha. 2021.  Continuous Release of Data Streams under both Centralized and Local Differential Privacy. In _CCS_. 1237–1253.
  * Weggenmann and Kerschbaum (2021) Benjamin Weggenmann and Florian Kerschbaum. 2021.  Differential Privacy for Directional Data. In _CCS_. 1205–1222.
  * Xiao and Xiong (2015) Yonghui Xiao and Li Xiong. 2015.  Protecting locations with differential privacy under temporal correlations. In _ACM SIGSAC Conference on Computer and Communications Security_. 1298–1309.
  * Xiong et al. (2020) Xingxing Xiong, Shubo Liu, Dan Li, Zhaohui Cai, Xiaoguang Niu, and Angel M. Del Rey. 2020\.  A Comprehensive Survey on Local Differential Privacy.  _Sec. and Commun. Netw._ (jan 2020).
  * Yang et al. (2022) Jianyu Yang, Xiang Cheng, Sen Su, Huizhong Sun, and Changju Chen. 2022.  Collecting Individual Trajectories under Local Differential Privacy. In _MDM_. 99–108.
  * Yang et al. (2020) Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok-Yan Lam. 2020.  Local differential privacy and its applications: A comprehensive survey.  _arXiv preprint arXiv:2008.03686_ (2020).
  * Yuan et al. (2023) Quan Yuan, Zhikun Zhang, Linkang Du, Min Chen, Peng Cheng, and Mingyang Sun. 2023\.  PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information. In _USENIX Security_.
  * Zeighami et al. (2022) Sepanta Zeighami, Ritesh Ahuja, Gabriel Ghinita, and Cyrus Shahabi. 2022.  A Neural Database for Differentially Private Spatial Range Queries. In _VLDB_. 1066–1078.
  * Zhang et al. (2018) Zhikun Zhang, Tianhao Wang, Ninghui Li, Shibo He, and Jiming Chen. 2018.  CALM: Consistent adaptive local marginal for marginal release under local differential privacy. In _CCS_. 212–229.
  * Zhang et al. (2021) Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. 2021\.  PrivSyn: Differentially Private Data Synthesis. In _30th USENIX Security Symposium (USENIX Security 21)_. 929–946.