arXiv CSopen access

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data Gaoyi Chen, Yan Huang, and Chenxi Qiu University of North Texas Denton, Texas, USA

arXiv:2605.26351v1 [cs.CR] 25 May 2026

Abstract Metric Differential Privacy (mDP) generalizes differential privacy by allowing privacy guarantees to be expressed with respect to an arbitrary distance metric over secrets. While mDP has been adopted in geo-location protection, most existing mechanisms perturb each location record in isolation and do not model how contextual information (e.g., recent mobility history) affects the utility of the released data. This mismatch is particularly pronounced for vehicle mobility traces, where service quality often depends on temporally correlated locations. In this paper, we propose Context-aware mDP (C-mDP), a framework for vehicle location privacy that incorporates contextual dependencies into both the utility model and the privacy notion. CmDP treats the protected secret as a context-augmented record and enforces metric indistinguishability over this augmented domain. We formulate optimal C-mDP mechanism design as a linear program (LP) that minimizes expected utility loss subject to C-mDP constraints. To improve scalability, we exploit conditional-independence structure between the current location and contextual variables to derive a reduced formulation with substantially fewer decision variables and constraints. We evaluate C-mDP on real-world vehicle mobility datasets and compare it with standard mDP baselines. The results show that C-mDP consistently achieves higher utility under the same privacy budget while satisfying the required metric privacy guarantees.

Keywords Metric differential privacy, data perturbation ACM Reference Format: Gaoyi Chen, Yan Huang, and Chenxi Qiu. 2026. Context-Aware Metric Differential Privacy for Vehicle Trajectory Data. In . ACM, New York, NY, USA, 17 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

Introduction

Within the spectrum of data privacy protection mechanisms, data perturbation has emerged as a widely adopted approach for protecting users’ sensitive information. The central idea is to deliberately inject noise into data, so that personal information remains unintelligible to unauthorized parties even in the event of server-side Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference’17, July 2017, Washington, DC, USA © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YY/MM https://doi.org/10.1145/nnnnnnn.nnnnnnn

Gas station

𝑦

𝑥𝑡

𝑥𝑡−1

Gas station

𝑦

𝑥𝑡 and 𝑦 have significantly different traveling costs to the gas station

𝑥𝑡

𝑥𝑡−1 𝑥𝑡 and 𝑦 have similar traveling costs to the gas station

(a)

(b)

Figure 1: Example: Different context information could cause different impacts in geo-location perturbation. 𝑥𝑡 and 𝑥𝑡 −1 are the current location and the location in the last time slot, respectively. 𝑦 is the perturbed location of 𝑥𝑡 . breaches. Among perturbation-based methods, Differential Privacy (DP) [16] has become the standard paradigm due to its rigorous, provable privacy guarantees. Differential privacy (DP) requires a mechanism to produce “indistinguishable” outputs on any two neighboring databases that differ in at most one record (i.e., have Hamming distance at most one). This framework has been generalized to metric Differential Privacy (mDP), which accommodates arbitrary distance metrics over diverse data domains [13]. Unlike DP, mDP defines neighboring data records via an underlying metric space and scales the indistinguishability guarantees according to the (non-binary) distances between records. mDP has been successfully applied to the release of sensitive geo-location data [4], using distance measures such as Manhattan, Euclidean, and Haversine distances. Compared to standard (Hamming-based) DP, optimizing mDP introduces additional challenges due to heterogeneous privacy requirements between neighboring records and the direction- and magnitude-dependent sensitivity of utility loss to perturbations. To minimize the utility loss induced by perturbations, several works on mDP have adopted a Linear Programming (LP) framework [8, 30, 32, 35, 36]. These approaches primarily focus on discrete domains, where the utility loss associated with each perturbation outcome can be quantified explicitly, and the LP directly optimizes the perturbation probability distribution to minimize the expected utility loss. However, these mDP methods primarily concentrate on optimizing perturbations for individual records without accounting for how contextual information affects utility loss. This limits the practical applicability of mDP in real-world scenarios, where the impact of data perturbations on data utility is influenced by the contextual aspects of the data. Motivating example. Consider a location-based service (LBS) that recommends the nearest point of interest (POI), such as a gas station, to a moving vehicle. To provide recommendations, the vehicle shares its location with the LBS server, which then estimates the traveling distance from the vehicle to candidate POIs. The utility

Conference’17, July 2017, Washington, DC, USA

of a reported (perturbed) location depends on how accurately the server can estimate the actual travel distance from the vehicle to each POI using the reported location. As illustrated in Fig. 1(a) and (b), the vehicle’s context, including its current location 𝑥𝑡 and preceding location 𝑥𝑡 −1 , plays an important role in determining utility. In Fig. 1(a), the vehicle is heading in a south-west direction, while in Fig. 1(b), it is moving north-east. If the current location 𝑥𝑡 is perturbed to the same point 𝑦, which is positioned south-west of 𝑥𝑡 , the resulting utility losses differ significantly between the two contexts: In Fig. 1(a), the estimated travel distance from 𝑦 to the gas station is similar to the actual travel distance from 𝑥𝑡 to the gas station, leading to a low utility loss. Conversely, in Fig. 1(b), the estimated travel distance from 𝑦 to the gas station deviates significantly from the actual distance, resulting in a higher utility loss. This example shows that the utility loss incurred when perturbing the current location 𝑥𝑡 to 𝑦 is context-dependent: it is much smaller in Fig. 1(a) than in Fig. 1(b). Motivated by this observation, we aim to minimize perturbation-induced utility loss by selecting perturbed locations according to their context-dependent utility. For instance, in scenarios like Fig. 1(a), location 𝑦 should be assigned higher probability because it leads to lower utility loss than it does in scenarios like Fig. 1(b).

1.1

Our Work

Contribution 1: Context-aware mDP (C-mDP). To fill the identified research gap, this paper introduces a new data perturbation framework called C-mDP. In contrast to conventional mDP, where the selection of perturbed data relies solely on the secret target record, C-mDP incorporates contextual information when determining the perturbation data distribution. By incorporating this contextual data, the framework explicitly accounts for its impact on utility loss caused by perturbation, an aspect that, to the best of our knowledge, has not been explored in other LP-based approaches. At the same time, C-mDP ensures that information disclosure remains bounded by a predefined threshold, as formally demonstrated in Proposition 1. Contribution 2: Efficient computation of C-mDP. Like [18], we frame the task of optimizing C-mDP as an LP problem, of which the objective is to minimize the expected data utility loss while ensuring the indistinguishability criterion of neighboring records. Considering that directly incorporating context data into the perturbation derivation significantly increases the complexity of LP, we reduce C-mDP by including only the “Markov blanket” (Definition 5) of the target secret records when optimizing the perturbation distribution of secret records. We theoretically prove that the reduced C-mDP can still satisfy the desired privacy criterion (Proposition 2) while achieving the minimum data utility loss (Proposition 3). We also design a Markov Blanket Identification (MBI) framework to identify the Markov blanket of secret data via conditional independence testing [38] and predict it using a deep neural network. Contribution 3: Empirical study of C-mDP in geo-location data privacy protection. As an example, we apply C-mDP to protect vehicle location privacy in location-based services (LBSs), where contextual data includes vehicles’ historical locations. Experimental results using two real-world taxicab datasets from "Rome,

Trovato et al.

Italy" [9] and "Porto, Portugal" [1] show that (1) the impact of context information on utility loss in LBS varies across time, regions, speed ranges, and cities, and (2) incorporating context information into existing LP-based perturbation reduces average data utility loss by at least 15.6% and 4.9% on the Rome and Porto datasets, respectively, compared to the benchmarks [21, 29, 35]. The rest of the paper is organized as follows: Section 2 gives the preliminaries of mDP. Sections 3 and 4 introduce the problem formulation and the algorithm design of C-mDP. Section 5 evaluates the performance of C-mDP. Section 6 presents the related work. Finally, Section 7 concludes the paper.

2

Technical Preliminaries

In this section, we first introduce the preliminaries of mDP (Section 2.1), the threat model and the countermeasure (Section 2.2), and the LP-based computation framework (Section 2.3). Table 3 in Appendix A lists the main notations used throughout this paper.

2.1

mDP

Generally, a data perturbation mechanism can be represented as a probabilistic function 𝑄: X → Y, where X and Y are the secret dataset and the perturbed dataset, respectively. We define the measure 𝑑 : X 2 → R to quantify the distance between records in X and denote the distance between any two secret records 𝑥𝑖 , 𝑥 𝑗 ∈ X by 𝑑𝑥𝑖 ,𝑥 𝑗 . We call two records 𝑥𝑖 , 𝑥 𝑗 ∈ X neighbors if their distance 𝑑𝑥𝑖 ,𝑥 𝑗 ≤ 𝜂, where 𝜂 > 0 is a pre-determined threshold. We use the random variable 𝑋 to represent the secret data (or secret record), and 𝑄 (𝑋 ) to represent its perturbed data. Definition 1. (mDP [4]) For any pair of neighboring records 𝑥𝑖 , 𝑥 𝑗 ∈ X (𝑑𝑥𝑖 ,𝑥 𝑗 ≤ 𝜂), 𝜖-mDP ensures that the probability distributions of their perturbed data 𝑄 (𝑥𝑖 ) and 𝑄 (𝑥 𝑗 ) are sufficiently close so that it is hard for an attacker to distinguish 𝑥𝑖 and 𝑥 𝑗 even if 𝑄 (𝑥𝑖 ) and 𝑄 (𝑥 𝑗 ) are breached to the attacker, which can be represented mathematically by, Pr [𝑄 (𝑋 ) = 𝑦|𝑋 = 𝑥𝑖 ]   ≤ 𝑒 𝜖𝑑𝑥𝑖 ,𝑥 𝑗 , ∀𝑦 ∈ Y. Pr 𝑄 (𝑋 ) = 𝑦|𝑋 = 𝑥 𝑗

(1)

Here, 𝜖 > 0 is called the privacy budget, reflecting how much information about the secret data 𝑋 is allowed to be disclosed from its perturbed representation 𝑄 (𝑋 ), i.e., lower 𝜖 implies a higher privacy level.

2.2

Threat Model and Countermeasure

Like the existing works [4], we assume that both perturbed data 𝑄 (𝑋 ) and perturbation function 𝑄 are known by attackers and users apply the function 𝑄 to perturb their secret data. An attacker can use Bayes’ formula [45] to derive the posterior of the secret data 𝑋 , i.e., Pr [𝑋 = 𝑥 |𝑄 (𝑋 ) = 𝑦], ∀𝑥 ∈ X, of which the accuracy can be quantified by the posterior leakage (Definition 2): Definition 2. (Posterior leakage [23] (PL)) Given the perturbation function 𝑄, the PL of any pair of neighboring records 𝑥𝑖 , 𝑥 𝑗 ∈ X s.t. 𝑑𝑥𝑖 ,𝑥 𝑗 ≤ 𝜂, , !
Pr [𝑋 = 𝑥𝑖 |𝑄 (𝑋 ) = 𝑦 ] Pr [𝑋 = 𝑥𝑖 ]     | (2) PL (𝑥𝑖 , 𝑥 𝑗 ); 𝑄 = sup | ln 𝑦

|

Pr 𝑋 = 𝑥 𝑗 |𝑄 (𝑋 ) = 𝑦 {z } posterior ratio

Pr 𝑋 = 𝑥 𝑗 | {z } prior ratio

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

Conference’17, July 2017, Washington, DC, USA

Intuitively, the prior ratio and the posterior ratio in Eq. (2) reflect the record 𝑋 ’s probabilities of being 𝑥𝑖 and 𝑥 𝑗 before and after the
observation of the perturbed data 𝑄 (𝑋 ) = 𝑦. If PL (𝑥𝑖 , 𝑥 𝑗 ); 𝑄 has a lower value, it implies that the attacker can obtain less additional information of 𝑋 by observing 𝑄 (𝑋 ), therefore achieving a higher privacy level. As a countermeasure against the Bayesian inference attacks, the perturbation function 𝑄 is designed to enforce the posterior leakage between any 𝑥𝑖 and 𝑥 𝑗 to be bounded by a threshold:
PL (𝑥𝑖 , 𝑥 𝑗 ); 𝑄 ≤ 𝜖𝑑𝑥𝑖 ,𝑥 𝑗 , ∀𝑥𝑖 , 𝑥 𝑗 ∈ X, (3) meaning that the perturbed data 𝑄 (𝑋 ) only discloses limited additional information to attackers. As proved by [4], meeting mDP as defined in Eq. (1) is sufficient to achieve the PL bound in Eq. (3).

2.3

Optimization of mDP using LP

Like [21, 35], we consider the case that both X and Y are finite. As such, the perturbation function 𝑄 can be represented as the perturbation matrix Q = 𝑞𝑥𝑖 ,𝑦𝑘 (𝑥 ,𝑦 ) ∈ X× Y , where each entry 𝑞𝑥𝑖 ,𝑦𝑘 𝑖 𝑘 denotes the probability of selecting 𝑦𝑘 ∈ Y as the perturbed data given the real record 𝑥𝑖 ∈ X. In this case, the mDP constraints formulated in Eq. (1) can be written as the following linear constraints: For each pair of neighboring records 𝑥𝑖 , 𝑥 𝑗 ∈ X s.t. 𝑑𝑥𝑖 ,𝑥 𝑗 ≤ 𝜂, 𝑞𝑥𝑖 ,𝑦𝑘 𝜖𝑑 ≤ 𝑒 𝑥𝑖 ,𝑥 𝑗 , ∀𝑦𝑘 ∈ Y. 𝑞𝑥 𝑗 ,𝑦𝑘

(4)

Additionally, the sum probability of perturbed record 𝑦𝑘 ∈ Y for each real record 𝑥𝑖 should be equal to 1 (probability unit measure), ∑︁ i.e., 𝑞𝑥𝑖 ,𝑦𝑘 = 1, ∀𝑥𝑖 ∈ X. (5) 𝑦𝑘 ∈ Y

We use 𝑐 𝑥𝑖 ,𝑦𝑘 to represent the data utility loss of the downstream decision-making caused by the perturbed record 𝑦𝑘 when the real record is 𝑥𝑖 . In practice, the assessment of each data utility loss, 𝑐 𝑥𝑖 ,𝑦𝑘 , depends on the specific manner in which the data is utilized in downstream decision-making processes. In the performance evaluation detailed in Section 5, we focus on location-based services (LBS) where vehicles are required to physically travel to fulfill tasks in spatial crowdsourcing scenarios [35] (e.g., picking up passengers). If a user’s reported location is inaccurate, the server will use the inaccurate location to estimate the travel cost from this user to the destination, causing estimation errors; in this case, the server might assign a vehicle that is too far away from the passenger. In such cases, the utility loss 𝑐 𝑥𝑖 ,𝑦𝑘 can be quantified using the discrepancy between the estimated and actual travel costs. By minimizing the utility loss, the system improves the likelihood of recommending the vehicle closest to the spatial task. The loss function of Q, measuring the expected utility loss caused by the perturbation matrix Q, can be defined as ∑︁ L (Q) = 𝑃 (𝑋 = 𝑥𝑖 ) · 𝑐 𝑥𝑖 ,𝑦𝑘 · 𝑞𝑥𝑖 ,𝑦𝑘 , (6) 𝑥𝑖 ∈ X,𝑦𝑘 ∈ Y

which is a linear function of Q. The goal of optimizing the perturbation matrix Q is to minimize L (Q) while satisfying both the mDP (Eq. (4)) and the probability unit measure (Eq. (5)), which can be

formulated as the following LP problem: min

L (Q)

(7)

s.t.

Eq. (4)(5) are satisfied,

(8)

where each entry 𝑞𝑥𝑖 ,𝑦𝑘 in Q satisfies 0 ≤ 𝑞𝑥𝑖 ,𝑦𝑘 ≤ 1.

3

Context-Aware mDP

We adopt an LP-based approach to optimize the selection probabilities of perturbed outputs, with the objective of minimizing the expected utility loss. This formulation requires explicitly quantifying the utility loss associated with each possible perturbed data point. As illustrated in Fig. 1, the impact of perturbation on data utility may vary significantly across different contexts, highlighting the necessity of incorporating contextual information when evaluating utility loss and determining perturbation probabilities. Motivated by this observation, we propose a new data perturbation framework, termed Context-aware mDP (C-mDP). We first define the C-mDP problem in Section 3.1 and then present a reduction in problem complexity in Section 3.2.

3.1

Problem Formulation

In C-mDP, the perturbation distribution for a secret record 𝑋 is allowed to depend not only on 𝑋 itself but also on contextual information 𝑉𝑋 associated with 𝑋 . Consider Fig. 1: when perturbing a vehicle’s current location 𝑥𝑡 , the probability of reporting each perturbed location can vary with the prior location 𝑥𝑡 −1 , since different 𝑥𝑡 −1 values indicate different movement directions and mobility patterns. More broadly, we treat 𝑉𝑋 as any context that can affect the utility (and potentially the effective privacy risk) of releasing a perturbed version of 𝑋 . In our vehicle-location case study (Section 5), 𝑋 is the vehicle’s current location at time 𝑡, and 𝑉𝑋 consists of its historical locations. We use 𝑉𝑋 to estimate the distribution of future locations, which is essential for supporting high-quality LBS under realistic latency. Importantly, while imperfect modeling of 𝑉𝑋 may introduce error in utility-loss estimation, it does not weaken the formal privacy guarantee: the mDP constraints are enforced directly on the mechanism. At the same time, incorporating historical context enables a more faithful assessment of utility impact than context-agnostic perturbation. We use V to denote the space of contextual information (i.e., 𝑉𝑋 ∈ V). We assume that both the secret record 𝑋 and its associated context 𝑉𝑋 are available to the user, which runs the perturbation locally, while the server observes only the released output and does not directly observe the realized 𝑉𝑋 . Accordingly, the perturbation function 𝑄 is defined as a mapping 𝑄 : X × V → Y, and the released (perturbed) value is denoted by 𝑄 (𝑋, 𝑉𝑋 ) given the real record 𝑋 and its context 𝑉𝑋 . The corresponding perturbation matrix is  Q = 𝑞 (𝑥𝑖 ,v),𝑦𝑘 (𝑥 ,v,𝑦 ) ∈ X× V × Y , (9) 𝑖

𝑘

where each entry 𝑞 (𝑥𝑖 ,v),𝑦𝑘 denotes the probability of outputting 𝑦𝑘 when the real record is 𝑋 = 𝑥𝑖 and the context is 𝑉𝑋 = v. 3.1.1 Expected Data Utility Loss. We use 𝑐 (𝑥𝑖 ,v),𝑦𝑘 to denote the utility loss incurred when the real record is 𝑥𝑖 with context v and the released (perturbed) record is 𝑦𝑘 . Accordingly, the expected utility loss induced by the perturbation matrix Q is

Conference’17, July 2017, Washington, DC, USA

L (Q) =

∑︁

Trovato et al.

𝑝 (𝑥𝑖 ,v) · 𝑐 (𝑥𝑖 ,v),𝑦𝑘 · 𝑞 (𝑥𝑖 ,v),𝑦𝑘 ,

(10)

(𝑥𝑖 ,v),𝑦𝑘

where 𝑝 (𝑥𝑖 ,v) is the prior probability that the secret record and its context are (𝑥𝑖 , v). In practice, the assessment of each data utility loss 𝑐 (𝑥𝑖 ,v),𝑦𝑘 is contingent on the specific manner in which data is processed in downstream decision-making. In the performance evaluation in Section 5, we consider the LBS services where vehicles need to physically travel to designated locations to receive desired services such as navigation [41], or to fulfill tasks in spatial crowdsourcing [35]. In those applications, 𝑐 (𝑥𝑖 ,v),𝑦𝑘 can be quantified by the discrepancy between the estimated travel cost (from 𝑦𝑘 to the destination) and actual travel cost (from 𝑥𝑖 to the destination). While we use vehicle geo-location protection as a concrete instantiation, the proposed framework is not limited to this scenario. It readily extends to other applications with only minor modifications, as long as one can characterize how perturbing the released data affects the resulting utility loss (e.g., through an applicationspecific loss function or objective). 3.1.2 Privacy Constraints. In Definition 3, we extend the PL constraints in Definition 2 to the context-aware PL constraints: Definition 3. (Context-aware PL and its bound) Using the perturbation function 𝑄, the context-aware PL of any pair of neighboring records 𝑥𝑖 , 𝑥 𝑗 ∈ X given their context data v and v′ is defined by
PL (𝑥𝑖 , v), (𝑥 𝑗 , v′ ) (11) , ! =

Pr [ (𝑋 , 𝑉𝑋 ) = (𝑥𝑖 , v) |𝑄 (𝑋 , 𝑉𝑋 ) = 𝑦 ]   sup | ln Pr (𝑋 , 𝑉𝑋 ) = (𝑥 𝑗 , v′ ) |𝑄 (𝑋 , 𝑉𝑋 ) = 𝑦 𝑦 | {z } posterior ratio

𝑝 (𝑥𝑖 ,v) | 𝑝 (𝑥 𝑗 ,v′ ) | {z } prior ratio

The corresponding context-aware privacy-loss (PL) bound is
PL (𝑥𝑖 , v), (𝑥 𝑗 , v′ ) ≤ 𝜖 𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) ,

(12)

where 𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) is the context-aware distance between the augmented secrets (𝑥𝑖 , v) and (𝑥 𝑗 , v′ ). We define this distance as an augmentation of the base Haversine distance between individual locations (i.e., the great-circle distance between two geographic points on the Earth computed from their latitudes and longitudes) as follows: 𝑑 (𝑥𝑡 ,v),(𝑥𝑡′ ,v′ ) ≜ 𝑑𝑥𝑡 ,𝑥𝑡′ +

Γ ∑︁

𝑤𝑡 −𝜏 𝑑 𝑣𝑡 −𝜏 ,𝑣𝑡′ −𝜏 ,

(13)

𝜏=1

where v = (𝑣𝑡 −1, ..., 𝑣𝑡 −Γ ) and 𝑤𝑡 −𝜏 (𝜏 = 1, ..., Γ) are decay weights that control the relative importance of protecting past locations. Notably, while incorporating context can improve utility modeling and utility in practice, it may also cause the released output 𝑌 to reveal information about the (unobserved) context 𝑉𝑋 . Our framework explicitly accounts for this via the context-aware PL definition over (𝑋, 𝑉𝑋 ) and the corresponding C-mDP constraints, which bound the adversary’s posterior gain for any pair of hypotheses (𝑥, v) and (𝑥 ′, v′ ). Proposition 1. To satisfy the context-aware PL bound in Eq. (12), it is sufficient to enforce the C-mDP constraints 𝑞 (𝑥𝑖 ,v),𝑦𝑘 − 𝑒

𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ )

· 𝑞 (𝑥 𝑗 ,v′ ),𝑦𝑘 ≤ 0, ∀𝑦𝑘 ∈ Y,

(14)

for every pair of neighboring records (𝑥𝑖 , v), (𝑥 𝑗 , v′ ) ∈ X × V, i.e., those with 𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) ≤ 𝜂.

Due to the limited space, the detailed proof of Proposition 1, as well as the proofs of Propositions 2–3 presented subsequently, are available in Appendix. 3.1.3 LP Formulation. Given the newly defined data utility loss (Eq. (10)) and C-mDP constraints (Eq. (14)), we formulate the C-mDP problem as the following LP problem: ∑︁ min L (Q) = 𝑝 (𝑥𝑖 ,v) · 𝑐 (𝑥𝑖 ,v),𝑦𝑘 · 𝑞 (𝑥𝑖 ,v),𝑦𝑘 (15) (v,𝑥𝑖 ),𝑦𝑘

s.t.

C-mDP (Eq. (14)) is satisfied Í 𝑦𝑘 ∈ Y 𝑞 (𝑥𝑖 ,v),𝑦𝑘 = 1, ∀𝑥𝑖 , v

(16) (17)

𝑞 (𝑥𝑖 ,v),𝑦𝑘 ∈ [0, 1], ∀𝑥𝑖 , 𝑦𝑘 , v.

(18)

The decision variables  in the above LP formulation (Eq. (15)–(18)) are the matrix Q = 𝑞 (𝑥𝑖 ,v),𝑦𝑘 (𝑥 ,v,𝑦 ) ∈ X× V × Y , including a total 𝑖 𝑘 of 𝑂 (|X||Y||V |) decision variables (entries) and 𝑂 (|X| 2 |Y||V |) linear constraints, where | · | denotes the set cardinality. Such a high complexity of the LP formulation renders it hard to apply in large-scale or time-sensitive applications. Discussion (C-mDP vs. context-free mDP). Notably, standard mDP mechanisms considered in our baselines are context-free: they learn a single perturbation distribution 𝑞𝑥,𝑦 for each location 𝑥 ∈ X and apply it regardless of any (unobserved) contextual information. In our notation, this is equivalent to additionally enforcing 𝑞 (𝑥,v),𝑦 = 𝑞 (𝑥,v′ ),𝑦 ,

∀𝑥 ∈ X, ∀v, v′ ∈ V, ∀𝑦 ∈ Y,

(19)

i.e., the perturbation distribution is invariant across contexts. By contrast, C-mDP allows context-conditioned mechanisms 𝑞 (𝑥,v),𝑦 (or 𝑞 (𝑥,b),𝑦 under the CD policy), while still enforcing likelihoodratio constraints with the same privacy-budget parameter 𝜖 under an appropriate metric. When utility depends on mobility context (e.g., direction/speed affecting future-location prediction), removing the invariance constraint can reduce expected utility loss, which helps explain why our context-aware mechanisms can outperform context-free mDP baselines in utility.

3.2

Problem Complexity Reduction

In this section, we describe the method to reduce the complexity of C-mDP by leveraging the independence relationships between the secret data and the context information. We first give some key definitions as follows: Definition 4. (Conditional independence (CI)) Given a random variable 𝑋 and two sets of random variables 𝐴 and 𝐵, 𝑋 and 𝐴 are called “conditionally independent given 𝐵” if and only if Pr [𝐵] > 0 and Pr [𝑋 |𝐴, 𝐵] = Pr [𝑋 |𝐵], written as: 𝑋 ⊥ ⊥ 𝐴| 𝐵. Definition 5. (Markov blanket) Given the random variable 𝑋 , we call the set of random variables 𝐵𝑋 ⊆ 𝑉𝑋 a Markov blanket of 𝑋 in 𝑉𝑋 if its complement set 𝐵𝑋c = 𝑉𝑋 \𝐵𝑋 satisfies 𝑋 ⊥ ⊥ 𝐵𝑋c |𝐵𝑋 , i.e., 𝑋 and 𝐵𝑋c are conditionally independent given 𝐵𝑋 . Based on Definitions 4 and 5, we next formalize a conditionally dependent (CD) policy that restricts how the perturbation mechanism may use contextual information. Definition 6. (CD policy) Let 𝑋 be a secret record with associated context variables 𝑉𝑋 . Let 𝐵𝑋 ⊆ 𝑉𝑋 be a Markov blanket of 𝑋 within

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

Conference’17, July 2017, Washington, DC, USA

𝑉𝑋 , and let 𝐵𝑋c ≜ 𝑉𝑋 \ 𝐵𝑋 denote its complement. A perturbation function 𝑄 follows the CD policy if 𝑄 (𝑋, 𝑉𝑋 ) ⊥ ⊥ 𝐵𝑋c {𝑋, 𝐵𝑋 },

(20)

i.e., conditioned on 𝑋 and 𝐵𝑋 , the output distribution is independent of the remaining context variables. Equivalently, letting b = 𝜋 (v) denote the restriction of v to 𝐵𝑋 , for any 𝑥 ∈ X, v ∈ V, and 𝑦 ∈ Y, 𝑞 (𝑥,v),𝑦

≜

Pr[𝑄 (𝑋, 𝑉𝑋 ) = 𝑦 | 𝑋 = 𝑥, 𝑉𝑋 = v]

(21)

=

Pr[𝑄 (𝑋, 𝑉𝑋 ) = 𝑦 | 𝑋 = 𝑥, 𝐵𝑋 = b]

(22)

≜

𝑞 (𝑥,b),𝑦 .

(23)

Intuitively, the CD policy enables the computation of the perturbation function 𝑄 to focus solely on the context information pertinent to the protected secret data 𝑋 , which reduces the computational complexity without compromising data utility and privacy. By following the CD policy, the perturbation matrix is represented by Q = 𝑞 (𝑥𝑖 ,b),𝑦𝑘 (𝑥 ,b,𝑦 ) ∈ X× B× Y , where each 𝑞 (𝑥𝑖 ,b),𝑦𝑘 𝑖 𝑘 denotes the probability of selecting 𝑦𝑘 as the perturbed data given the real record 𝑋 = 𝑥𝑖 and the context information 𝐵𝑋 = b. We denote the space of the Markov blanket 𝐵𝑋 as B. By focusing exclusively on the context information within B rather than the entire context space V, the complexity of C-mDP is reduced. Next, we present theoretical proofs that, under Assumption 1, adhering to the CD policy preserves both the privacy criteria (as per Proposition 2) and the optimality (as per Proposition 3) of the perturbation matrix Q. Proposition 2. (PL guarantee) If a perturbation matrix Q follows the CD policy and satisfies the corresponding mDP constraints: 𝜖𝑑 ′ 𝑞 (𝑥𝑖 ,b),𝑦𝑘 − 𝑒 (𝑥𝑖 ,b),(𝑥 𝑗 ,b ) · 𝑞 (𝑥 𝑗 ,b′ ),𝑦𝑘 ≤ 0, ∀(𝑥𝑖 , b), (𝑥 𝑗 , b′ ), 𝑦𝑘 (24) where 𝑑 (𝑥𝑖 ,b),(𝑥 𝑗 ,b′ ) ≤ 𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) , it is sufficient for Q to achieve the bounded context-aware PL as defined in Eq. (12). Assumption 1. We assume that the data utility loss of a secret record is determined by (i) its prior distribution, (ii) the perturbation distribution applied to it, and (iii) a set of context-independent factors (constants) that do not vary across the secret record contexts, such as road topology or the underlying map. Accordingly, each utility loss 𝑐 (𝑥𝑖 ,v),𝑦𝑘 can be written as
𝑐 (𝑥𝑖 ,v),𝑦𝑘 = ℎ 𝑝 (𝑥𝑖 ,v) , 𝑞 (𝑥𝑖 ,v),𝑦𝑘 ; 𝜽 , (25) where 𝜽 denotes such constant factors. By the CD policy, we have
(26) 𝑐 (𝑥𝑖 ,v),𝑦𝑘 = ℎ 𝑝 (𝑥𝑖 ,v) , 𝑞 (𝑥𝑖 ,v),𝑦𝑘 ; 𝜽
= ℎ 𝑝 (𝑥𝑖 ,b) , 𝑞 (𝑥𝑖 ,b),𝑦𝑘 ; 𝜽 (27) =

𝑐 (𝑥𝑖 ,b),𝑦𝑘 .

(28)

Proposition 3. Given that Assumption 1 holds, the loss function L (Q) in Eq. (10) can be rewritten as the following reduced form: ∑︁ L (Q) = 𝑝 (𝑥𝑖 ,b) · 𝑐 (𝑥𝑖 ,b),𝑦𝑘 · 𝑞 (𝑥𝑖 ,b),𝑦𝑘 . (29) (𝑥𝑖 ,b),𝑦𝑘

Discussion. In our performance evaluation (Section 5), we instantiate the framework with vehicle assignment in spatial crowdsourcing, which aligns well with Assumption 1. In this setting, the platform’s decision quality is driven by travel-cost estimates computed from the reported (perturbed) worker locations and the fixed road

network. Hence, for a given worker–context secret (𝑥𝑖 , v), the expected utility loss under a reported location 𝑦𝑘 is determined by: (i) the prior 𝑝 (𝑥𝑖 ,v) over the worker’s true location under context v, (ii) the applied perturbation probability 𝑞 (𝑥𝑖 ,v),𝑦𝑘 , and (iii) contextindependent constants 𝜽 capturing the map/road topology and the assignment objective. By contrast, other mDP applications, such as text perturbation, may fall outside the scope of Assumption 1. In such cases, utility loss can depend not only on the distribution of protected tokens but also on their semantic meaning in different context, which can substantially influence downstream tasks (e.g., sentiment analysis). To accommodate scenarios where Assumption 1 does not hold, we outline a two-stage optimization strategy as a potential remedy; the details are provided in Appendix C. Finally, to derive the optimal perturbation matrix Q, we formulate the Reduced C-mDP problem as the following LP problem: min

L (Q) =

∑︁

𝑝 (𝑥𝑖 ,b) · 𝑐 (𝑥𝑖 ,b),𝑦𝑘 · 𝑞 (𝑥𝑖 ,b),𝑦𝑘

(30)

(𝑥𝑖 ,b),𝑦𝑘

s.t.

mDP (Eq. (24)) is satisfied ∑︁ 𝑞 (𝑥𝑖 ,b),𝑦𝑘 = 1, ∀𝑥𝑖 , b

(31) (32)

𝑦𝑘 ∈ Y

0 ≤ 𝑞 (𝑥𝑖 ,b),𝑦𝑘 ≤ 1, ∀𝑥𝑖 , 𝑦𝑘 , b,

(33)

of  which the decision variables are the entries in the matrix Q = 𝑞 (𝑥𝑖 ,b),𝑦𝑘 (𝑥 ,b,𝑦 ) ∈ X× B× Y , including a total of 𝑂 (|X||Y||B|) deci𝑖 𝑘 sion variables and 𝑂 (|X| 2 |Y||B|) linear constraints, which achieves a lower complexity compared to the original C-mDP formulated in Eq. (15)–(18). To simplify, hereafter, when we refer to “C-mDP”, we are indicating its reduced form (Eq. (30)–Eq. (33)). Here, we emphasize that the privacy parameter 𝜖 in our paper is an output-privacy budget: it bounds the information leaked about an individual user only through the released perturbed output 𝑌 = 𝑄 (𝑋, 𝐵𝑋 ) at run time. Although Q is obtained by solving the above LP, this computation is performed offline and the resulting Q is fixed for deployment; it is therefore not an interactive runtime process that repeatedly queries users’ records and releases additional per-user information. In particular, the LP coefficients are constructed from (i) distances/utility components defined on the location domain (derived from the public map data in OpenStreetMap [2]) and (ii) population-level prior statistics estimated offline from a representative trajectory dataset (e.g., using 330k trajectories, with a separate held-out set for evaluation). After Q is fixed, each user/device perturbs only its own (𝑋, 𝐵𝑋 ) locally by sampling from the corresponding row of Q, and the only information released about that user’s record is 𝑌 , whose leakage is bounded by the C-mDP constraints with parameter 𝜖.

4

Markov Blanket Identification

Within the computation framework outlined in Section 3.2, solving the reduced C-mDP requires the identification of the Markov blanket 𝐵𝑋 for the secret record 𝑋 . In this section, we present our Markov Blanket Identification (MBI) framework. To illustrate, we apply MBI in the context of vehicle privacy protection, where vehicles need to report perturbed locations to a central server [35].

Conference’17, July 2017, Washington, DC, USA

4.1

Trovato et al.

Additional Assumptions and Notations

Vehicle trajectory dataset

Features:

Typically, the design of MBI relies on the two assumptions [42]:

samples

CI_Test

CI_Test CI_Test

Markov blanket 𝐵𝑋𝑡

Reject Fail to Rej.

Reject Fail to Rej.

(a) Markov Blanket Discovery Hidden layers …

…

…

Input Training dataset Input layer: Features {Time interval, Speed range, Region} + Hypothesis ℋ𝟎

…

4.2.1 Stage (a): Markov Blanket Discovery. We first carry out an empirical study on the taxicab trajectory datasets from two different cities, "Rome, Italy" [9] and "Porto, Portugal" [1] to analyze the dependence of Markov blankets on factors including vehicle speed, geographic regions (e.g., downtown vs suburban areas), and time (e.g., peak hours vs off-peak hours). In contrast to many existing studies (e.g., [37]) that assume the mobility of vehicles follows a first-order Markov process (so that a Markov blanket contains only one preceding location), our discovery reveals a notable variation in the Markov blankets given the different factors. The detailed results of the empirical study can be found in Section 5.1.

ℋ𝟎 …

CI_Test

…

Methodology

Fig. 2 shows the framework of Markov Blanket Identification, including two stages (a) Markov Blanket Discovery and (b) Markov Blanket Prediction.

samples

…

4.2

{11 pm-12 pm, 65-70 miles/h, Region 20}

ℋ𝟎 …

…

…

In the context of vehicle location privacy protection, the secret record 𝑋𝑡 - representing the location of a target vehicle at time 𝑡 - is correlated to the vehicle’s preceding locations 𝑉𝑋𝑡 = {𝑋𝑡 −1, ..., 𝑋𝑡 −𝑇 } at time slots 𝑡 − 1, ..., 𝑡 − 𝑇 , where 𝑇 is the size of 𝑉𝑋𝑡 . This dependency can be naturally modeled by a higher-order Markov process [31], commonly seen as a special case of Bayesian networks. Note that our methodology remains applicable in general mDP applications given the two assumptions (A1) and (A2) hold. To test the CI between 𝑋𝑡 and its context variables 𝑉𝑋𝑡 , we employ a statistical CI test using analytic kernel embeddings of location distributions [38]. Specifically, the CI testing summarizes the evidence in the observational data against a null hypothesis H0 : 𝑋𝑡 ⊥⊥ 𝑋𝑡 −𝑙 |𝐵𝑋𝑡 (𝑋𝑡 −𝑙 ∈ 𝑉𝑋𝑡 \𝐵𝑋𝑡 ), and returns a 𝑝-value, representing the probability of making a Type I error - rejecting H0 when it is true. If 𝑝-value ≤ 0.05, it is typically considered to be statistically significant, in which case we reject H0 ; otherwise, we fail to reject H0 [6]. Notably, identifying the Markov blanket requires performing CI testing between protected records and their context variables, which has relatively high time complexity [38]. As a result, it becomes challenging to identify the Markov blanket in real-time due to the time-sensitive nature of vehicle location reports. This challenge motivates us to predict 𝐵𝑋𝑡 using a pre-trained deep neural network (DNN) rather than performing CI testing during each perturbation. The DNN establishes an empirical relationship between 𝐵𝑋𝑡 and the features that possibly influence vehicle mobility, including speeds, regions, and time. This relationship, represented as a function 𝑓 (𝑡𝑖𝑚𝑒, 𝑠𝑝𝑒𝑒𝑑, 𝑟𝑒𝑔𝑖𝑜𝑛, H0 ), returns either “Reject” or “Fail to reject” for the hypothesis H0 , which enables the vehicle to promptly identify the Markov blanket of its location based on its current states {𝑡𝑖𝑚𝑒, 𝑠𝑝𝑒𝑒𝑑, 𝑟𝑒𝑔𝑖𝑜𝑛} without doing the CI test that might introduce significant delays.

Step ② - Markov blanket est.

…

{12 pm-1 am, 20-25 miles/h, Region 1}

Step ① - Dataset partitioning

…

(A1) the data under consideration was generated by a Bayesian network faithful to it, and (A2) there exists a reliable statistical method for testing the CI between the target random variables.

{Time interval, Speed range, Region}

Markov blanket 𝐵𝑋𝑡

Output Training dataset Output layer: “Reject” or “Fail to reject”

The DNN to establish an empirical relationship 𝒇(·) (b) Markov Blanket Prediction

Figure 2: Markov blanket identification framework. 1 Dataset partitioning. Considering the variance of Step ○: Markov blankets under different features, as Fig. 2(a) shows, we partition the initial dataset into groups according to the combination of the features {𝑡𝑖𝑚𝑒, 𝑠𝑝𝑒𝑒𝑑, 𝑟𝑒𝑔𝑖𝑜𝑛}. This ensures that the Markov blankets within each sample group exhibit a relatively consistent pattern (with each group comprising a minimum of 200 samples): (1) Time: According to the 24-hour time format, we categorize the trajectories into 24 groups [12 am–1 am), [1 am–2 am), ..., [11 pm– 12 am) on the UTC +0 timestamps provided in the initial dataset. (2) Speed: We calculate the average speed of each examined subtrajectory {𝑋𝑡 , 𝐵ˆ𝑋𝑡 }, comprising the current location 𝑋𝑡 and the tested Markov blanket 𝐵ˆ𝑋𝑡 . We divide all the sub-trajectories into groups of 5 mph intervals across the entire speed range from 0 to 120 mph. (3) Regions: For the Rome dataset, we use a bounding box from 41.64°N to 42.12°N and 12.23°E to 12.83°E as the approximated boundary of Rome city, and divide the whole region into 4×5 subregions with each cell size 12’×12’, then we categorize the sub-trajectories {𝑋𝑡 , 𝐵ˆ𝑋𝑡 } into 20 groups based on their located regions. For the Porto dataset, the approximated boundary of the bounding box is 41.03°N to 41.27°N and 8.49°E to 8.73°E, and it is divided into 3×3 subregions with each cell size 8’×8’, then we categorize the sub-trajectories into 9 groups based on their located regions. 2 Markov blanket identification. Following the dataset Step ○: partitioning, we proceed to estimate the Markov blanket 𝐵𝑋𝑡 of locations 𝑋𝑡 in each sample group. By assuming the locations in 𝑉𝑋𝑡 with closer time stamps to the current location as more correlated, we test the locations in 𝑉𝑋𝑡 in the order of decreasing time stamps. Algorithm 1 shows the pseudocode: It initializes 𝐵𝑋𝑡 by 𝑋𝑡 −1 (lines 1 and 4). After that, in each iteration 𝑚, it applies the function CI_test() [38] to test the null hypothesis H0 : 𝑋𝑡 ⊥ ⊥ 𝑋𝑡 −𝑚−1 |𝐵𝑋𝑡 (lines 2-7). If H0 is rejected, i.e. 𝑝-value ≤ 0.05, then we add 𝑋𝑡 −𝑚 to

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

Conference’17, July 2017, Washington, DC, USA

2 Algorithm 1: Markov blanket identification in Step ○.

5

Input : Samples of 𝑋𝑡 and its context variables 𝑉𝑋𝑡 Output : Markov blanket 𝐵𝑋𝑡 1 Let 𝐵𝑋𝑡 be an empty Markov blanket; 2 𝑚 ← 1; // Iteration index 3 do 4 Add 𝑋𝑡 −𝑚 to 𝐵𝑋𝑡 ; 5 𝑝-value ← CI_Test(H0 : 𝑋𝑡 ⊥ ⊥ 𝑋𝑡 −𝑚−1 | 𝐵𝑋𝑡 ); 6 Increase 𝑚 by 1; 7 while 𝑝-value ≤ 0.05; 8 return 𝐵𝑋𝑡 ;

In this section, we evaluate our proposed context-aware mechanism, LP+C-mDP, in a vehicle-based LBS setting [30, 36], where a central server collects a perturbed location report from a participating vehicle and recommends a destination (e.g., for navigation or spatial crowdsourcing). We use two real-world taxicab mobility datasets from Rome, Italy and Porto, Portugal: Rome contains 367,052 trajectories from 320 taxis over 30+ days1 , and Porto contains 1,666,766 trajectories from 442 taxis over 540 days2 ; each record includes a timestamp and GPS coordinates. For each city, we map trajectories onto a road network extracted from OpenStreetMap [2] and model the network as a weighted directed graph [35] (Rome: 43,160 nodes/89,739 edges; Porto: 5,033 nodes/10,537 edges). We begin with an empirical study in Section 5.1 that characterizes conditional dependencies in the mobility traces, and thus the effective Markov blanket size, across coarse factors such as region, speed, and time, motivating adaptive context selection. Section 5.2 then evaluates the accuracy and inference latency of our Markov-Blanket Identification (MBI) module and compares utility loss across privacy budgets against representative mDP baselines. Finally, Section 5.3 reports computational efficiency, including both offline mechanism construction and online perturbation (sampling) costs.

𝐵𝑋𝑡 . The algorithm ends when the 𝑝-value returned by CI_test() is higher than 0.05 (line 7), indicating that the hypothesis H0 fails to be rejected. In this case, we do not reject the Markov blanket 𝐵𝑋𝑡 and return it as the result (line 8). After Algorithm 1, we also label each Hypothesis H0 : 𝑋𝑡 ⊥ ⊥ 𝑋𝑡 −𝑚−1 |𝐵 with 𝐵𝑋𝑡 ⊂ 𝐵 ⊂ 𝑉𝑋𝑡 as “Fail to reject”. 4.2.2 Stage (b) Markov Blanket Prediction. Upon completing Stage (a), the status of each null hypothesis H0 is determined as either “Reject” or “Fail to reject” in each sample group sharing the same feature combination {𝑡𝑖𝑚𝑒, 𝑠𝑝𝑒𝑒𝑑, 𝑟𝑒𝑔𝑖𝑜𝑛𝑠}. As depicted in Fig. 2(b), we compile these features along with each H0 to create the input training dataset. The corresponding conclusions, “Reject” or “Fail to reject”, serve as the output training dataset. Algorithm 2: Markov blanket prediction using the pre-trained DNN. Input : Current speed, time, and region Output : Markov blanket 𝐵𝑋𝑡 1 Let 𝐵𝑋𝑡 be an empty Markov blanket; 2 𝑚 ← 1; // Iteration index 3 do 4 Add 𝑋𝑡 −𝑚 to 𝐵𝑋𝑡 ; 5 Indicator ← DNN(time, speed, region, 𝑚); 6 Increase 𝑚 by 1; 7 while Indicator = “Reject”; 8 return 𝐵𝑋𝑡 ;

Subsequently, a DNN is trained on this dataset to establish an empirical relationship 𝑓 , enabling the identification of whether a hypothesis H0 is tested as “Reject” or “Fail to reject” given the features {𝑡𝑖𝑚𝑒, 𝑠𝑝𝑒𝑒𝑑, 𝑟𝑒𝑔𝑖𝑜𝑛𝑠}. Algorithm 2 shows the detailed pseudocode of the Markov blanket prediction introduced in Stage (b). The inputs of the algorithm include the vehicle’s current speed, time, and region. The output is the predicted Markov blanket. The algorithm commences by initializing the Markov blanket 𝐵𝑋𝑡 using 𝑋𝑡 −1 (lines 1 and 4). Subsequently, in each iteration 𝑚, the algorithm leverages the pre-trained DNN() to predict whether it should “reject” or “fail to reject” the null hypothesis H0 : 𝑋𝑡 ⊥ ⊥ 𝑋𝑡 −𝑚−1 |𝐵𝑋𝑡 . The algorithm adds the preceding locations to 𝐵𝑋𝑡 sequentially (line 2-7), concluding when it “fails to reject” H0 (line 7), and returns 𝐵𝑋𝑡 as the identified Markov blanket (line 8).

5.1

Performance Evaluation

Correlation Between Time, Speed, Regions, and CI Testing

Table 1: Correlation between different features and the 𝑝values of the CI testing [38]. Features Region Long. Lat.

Correlation measures

Speed

Time

Pearson Spearman’s rank Kendall’s tau Type I error of CCIT

-0.4886 -0.7122 -0.5430 1.14e-30

Rome, Italy -0.0081 -0.0028 -0.0734 0.0124 -0.0539 0.0102 0.0974 0.3977

0.0410 0.0620 0.0420 0.2871

Pearson Spearman’s rank Kendall’s tau Type I error of CCIT

-0.1848 -0.1283 -0.1075 9.55e-10

Porto, Portugal -0.0913 0.0905 -0.2405 0.1144 -0.1804 0.0912 3.72e-14 0.2447

-0.0189 -0.0296 -0.0202 0.0152

Table 1 lists multiple statistical measures to demonstrate a correlation between 𝑝-values and the other features like speed, regions, and time. The correlation measures include Pearson’s correlation, Spearman’s rank, and Kendall’s tau, providing insights into the linear and rank-based relationships between the features. The Type I error rate of the CCIT3 testing is also included. The table reveals distinct correlation features between the selected features and 𝑝-values in the two cities. In Rome, speed exhibits a strong negative correlation with 𝑝-values across all three 1 https://ieee-dataport.org/open-access/crawdad-romataxi 2 https://www.kaggle.com/datasets/crailtap/taxi-trajectory 3 Classifier CI Test (CCIT) [39] is a non-parametric method that can test independence

between continuous random variables. In Table 1, if the probability of its Type I error is lower than 0.05, the null hypothesis is rejected, meaning that the 𝑝 -value of the CI test in [38] and the feature are not independent.

Conference’17, July 2017, Washington, DC, USA

correlation metrics, indicating that as speed increases, 𝑝-values tend to decrease. In Porto, speed also shows a negative correlation with 𝑝-values, and the CCIT results suggest that this relationship remains statistically significant, albeit much weaker than in Rome. The correlations between 𝑝-values and regions (Longitude and Latitude) in Rome are weak, and the CCIT values indicate that they are not statistically significant. However, Longitude shows a slightly stronger negative correlation with 𝑝-values in Porto. The time feature reveals a weak correlation in both cities. Next, we provide detailed empirical analysis of the correlation between regions, speed, and time, and the 𝑝-value of the CI test. (1) 𝑝-value vs. regions. As Fig. 3 and Fig. 4 show, we define the approximated boundary of Rome and Porto using two bounding boxes (as described earlier). Due to insufficient data in two regions of the Rome dataset, we excluded these two regions from our analysis (of which the bounding boxes are (i) from 42.00°N to 42.12°N and 12.71°E to 12.83°E, and (ii) from 41.64°N to 41.76°N and 12.71°E to 12.83°E, respectively). We test the null hypothesis H0 : 𝑋𝑡 ⊥⊥ 𝑋𝑡 −𝑚−1 |𝐵𝑋𝑡 for the trajectories using the CI test. In Fig. 3(a)-(e), we display the heatmap of the 𝑝-values returned by the CI test across the 18 regions in Rome when |𝐵𝑋𝑡 | = 1, 2, 3, 4, 5, respectively. The figures show that when 𝑚 = 1 or 2, the average 𝑝-value is higher in downtown compared to the suburban area, suggesting that the hypothesis H0 is more likely to be rejected in the suburban area than in downtown when 𝑚 = 1 or 2. The heatmap for Porto in Fig. 4(a)-(e) reveals different conclusions. When 𝑚 = 1, the average 𝑝-value is lower in downtown compared to the suburban area, and when 𝑚 = 2, all 𝑝-value turn relatively high. The varying 𝑝-values across regions reflect differences in vehicle mobility patterns. For example, vehicles may move more slowly in downtown areas (potentially leading to higher 𝑝-values) and faster in suburban areas (potentially resulting in lower 𝑝-values). (2) 𝑝-value vs. speeds. We calculate the average speed of each examined sub-trajectory {𝑋𝑡 , 𝐵ˆ𝑋𝑡 }, based on which we divide all the sub-trajectories into groups of 5 mph intervals across the entire speed range from 0 to 120 mph. We test the null hypothesis H0 for the trajectories in different speed intervals and display the corresponding 𝑝-values in the two cities in Fig. 5(a)(b), respectively, given |𝐵𝑋𝑡 | = 1, 2, 3, 4, 5. Results from both cities reveal a similar trend: within a certain range, speed is negatively correlated with the 𝑝-value, but beyond this range, the correlation becomes positive, forming a U-shaped pattern. In other words, at very low and very high speeds, we fail to reject the null hypothesis, indicating a high correlation between trajectory location points. Conversely, at intermediate speed levels, we reject the null hypothesis and accept the alternative hypothesis, suggesting lower correlation between trajectory location points. Specifically, in the Rome dataset, 𝑝-values reach their minimum within the speed range of 75 to 100, before rising again, while in the Porto dataset, this minimum occurs at a higher speed range, highlighting city-specific differences. (3) 𝑝-value vs. time intervals. According to the 24-hour time format, we group the trajectories as described earlier. We test the null hypothesis H0 for the trajectories in different time intervals and display the corresponding 𝑝-values when |𝐵𝑋𝑡 | = 1, 2, 3, 4, 5 in Fig. 6(a)-(e) and Fig. 7(a)-(e), respectively. We observe that when |𝐵𝑋𝑡 | = 3, 4, 5, all the 𝑝-values are close to 1 in both cities. Conversely, when

Trovato et al.

|𝐵𝑋𝑡 | = 1, 2, the 𝑝-values for Rome are relatively lower during the intervals 11-14 (11 am – 2 pm ), 17-18 (5 pm – 6 pm) and 22-23 (10 pm – 11 pm). This observation aligns with the findings in Fig. 5, where during these time intervals, vehicle traffic is relatively lower, indicating higher average vehicle speeds. Consistent with Fig. 5, 𝑝-values decrease as speed increases up to an intermediate range (approximately 75–100 mph) and then rise again. Conclusion. From all the figures above, we find the results of CI testing (the 𝑝-values) exhibit variations across different regions, time intervals, and speed intervals. This observation challenges the assumption made by many related works, which posit that targets’ mobility follows a first-order Markov process [11, 37]. Moreover, we observe that when more locations are encompassed in 𝐵𝑋𝑡 , there is a reduced likelihood of rejecting the null hypothesis H0 . This observation supports the design of MBI in Algorithm 1: If we fail to reject H0 , we consider that adding any additional locations to 𝐵𝑋𝑡 would further decrease the likelihood of rejecting H0 . As a result, we consider that 𝐵𝑋𝑡 has been successfully identified and label H0 : 𝑋𝑡 ⊥ ⊥ 𝑋𝑡 −𝑚−1 |𝐵 with 𝐵 ⊃ 𝐵𝑋𝑡 as “fail to reject”.

5.2

MBI Accuracy Evaluation

5.2.1 Experiment settings. We implement the MBI predictor in PyTorch [3] as a three-layer fully connected binary classifier (Fig. 2(b)) with ReLU activations and a sigmoid output. We split the dataset into training/validation/testing sets with a ratio of 60%, 20%, 20%. The model is pretrained offline and only used for fast Markovblanket prediction at runtime. As shown in Fig. 8, the average inference time is 0.1557 ms (Rome) and 0.1588 ms (Porto), and over 98% of predictions finish within 2 ms. Additional training details are provided in Appendix E. In our framework, we train the MBI module using the full cityscale trajectory corpus. We report utility/privacy of the proposed perturbation mechanism on a subset of about 500 trajectories; this evaluation subset is sampled from the same corpus and therefore may overlap with the training data. The full city-scale trajectories are used to learn population-level regularities (e.g., how dependency strength and Markov-blanket size vary with coarse features), while our formal privacy budget 𝜖 is defined for the online release 𝑌 = 𝑄 (𝑋, 𝑉𝑋 ) (details in Appendix E). 5.2.2 Experimental results. We display the performance of Markov Blanket Prediction in Table 2. The table shows that the prediction accuracy, defined as the proportion of instances that are accurately predicted, is 0.9512 and 0.9413 for Rome and Porto, respectively. Due to the imbalance between positive and negative samples, in order to capture the imbalanced binary classification of “reject” and “fail to reject”, we also test the precision, recall, and F1 score of the predictive model. In terms of positive F measures, the precision and recall for Rome are 0.9580 and 0.9868, for Porto are 0.9710 and 0.9630, suggesting that both models excel at identifying positive cases (“fail to reject”) with minimal false positives and negatives. The F1 scores, at 0.9722 and 0.9670, confirm the well-balanced trade-off between precision and recall, further demonstrating that the models effectively handle both errors. The high recall scores are particularly

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

(a) |𝐵𝑋𝑡 | = 1 and 𝑚 = 1

(b) |𝐵𝑋𝑡 | = 2 and 𝑚 = 2

Conference’17, July 2017, Washington, DC, USA

(c) |𝐵𝑋𝑡 | = 3 and 𝑚 = 3

(d) |𝐵𝑋𝑡 | = 4 and 𝑚 = 4

(e) |𝐵𝑋𝑡 | = 5 and 𝑚 = 5

Figure 3: Heatmap of 𝑝-values returned by the null hypothesis H0 across different regions in Rome, Italy.

(a) |𝐵𝑋𝑡 | = 1 and 𝑚 = 1

(b) |𝐵𝑋𝑡 | = 2 and 𝑚 = 2

(c) |𝐵𝑋𝑡 | = 3 and 𝑚 = 3

(d) |𝐵𝑋𝑡 | = 4 and 𝑚 = 4

(e) |𝐵𝑋𝑡 | = 5 and 𝑚 = 5

Figure 4: Heatmap of 𝑝-values returned by the null hypothesis H0 across different regions in Porto, Portugal. 1

1

|BXt| =1 |BXt| =2

0.6

|BXt| =3 |BXt| =4

0.4

|BXt| =5

0.2

0.05

|BXt| =1

0.8

p-value

p-value

0.8

|BXt| =2 0.6

|BXt| =3

0.4

|BXt| =4 |BXt| =5

0.2

0.05

0 0

25

50

75

100

125

150

175

The negative F1 score for Porto is slightly lower than Rome’s, suggesting that while Porto’s model is better at identifying negatives, the increased false negatives hinder its overall performance. Table 2: Prediction performance of DNN.

0 0

25

50

75

100

125

Speed (mile/hour)

Speed (mile/hour)

(a) Rome, Italy

(b) Porto, Portugal

150

175

Figure 5: Relationship between speeds and 𝑝-values. 𝑝-values are returned by the null hypothesis H0 given different speed ranges.

notable, indicating that the models are adept at identifying nearly all relevant positive instances, reducing the risk of missed detections. Additionally, we calculate the negative precision, negative recall, and negative F1 score by treating “reject” as a “negative instance”. These metrics specifically assess the model’s performance in predicting “reject”. We can see that the models’ performance declines when dealing with negative samples. For Rome, the table displays the negative precision and negative recall as 0.8972 and 0.7273. While the negative precision remains relatively high, the negative recall is notably lower, which suggests that the model is less effective in correctly identifying negative classes compared to its performance in the positive class, likely a result of the class imbalance within the dataset, where “fail to reject” dominates. For Porto, the negative precision drops to 0.7123, significantly lower than Rome’s 0.8972, indicating a higher rate of false negatives in predicting “reject” cases. However, negative recall improves, reflecting a better capability in detecting true negatives compared to Rome. The negative F1 score for Rome is 0.8033, which suggests that while the model maintains a reasonable balance, there remains some room for improvement.

City

Rome, Italy

Porto, Portugal

Metrics

Value

BCE loss Prediction accuracy Precision Recall F measures F1 score Negative precision Negative recall Negative F1 score

0.1211 0.9512 0.9580 0.9868 0.9722 0.8972 0.7273 0.8033

BCE loss Prediction accuracy Precision Recall F measures F1 score Negative precision Negative recall Negative F1 score

0.1321 0.9413 0.9710 0.9630 0.9670 0.7123 0.7610 0.7358

We observe that the model’s performance differs slightly between Rome and Porto, with Rome achieving higher overall prediction accuracy and a better balance in handling both positive and negative cases. Porto’s model, while more precise in predicting positive instances, struggles with higher false negatives when it comes to negative classification. Recall that the number of decision variables in the LP problem (Eq. (28)-(31)) is 𝑂 (|X||Y||B|), where |X|, |Y|, and |B| respectively denote the size of the secret dataset, the size of perturbed dataset, and the number of possible values of the random variables within the Markov blanket. Fig. 9 shows the distributions of the predicted

Conference’17, July 2017, Washington, DC, USA

0.5

0.4

Time threshold = 0.05

threshold = 0.05

(a) |𝐵𝑋𝑡 | = 1 and 𝑚 = 1

0.4

Time threshold = 0.05

Time threshold = 0.05

(b) |𝐵𝑋𝑡 | = 2 and 𝑚 = 2

0.5

0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

0

Time

1

0.6

0.2

0.2

0.2 0

1 0.8

0.6

p-value

0.4

1 0.8

(c) |𝐵𝑋𝑡 | = 3 and 𝑚 = 3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

0.6

p-value

p-value

0.8

p-value

1

1

p-value

Trovato et al.

Time threshold = 0.05

(d) |𝐵𝑋𝑡 | = 4 and 𝑚 = 4

(e) |𝐵𝑋𝑡 | = 5 and 𝑚 = 5

1 0.8

0.6 0.4

0.6 0.4

0.6 0.4

0.2

0.2

0

0

0

0

Time threshold = 0.05

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

0.2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

0.2

Time threshold = 0.05

(a) |𝐵𝑋𝑡 | = 1 and 𝑚 = 1

(b) |𝐵𝑋𝑡 | = 2 and 𝑚 = 2

Time threshold = 0.05

(c) |𝐵𝑋𝑡 | = 3 and 𝑚 = 3

0.6 0.4 0.2

Time threshold = 0.05

(d) |𝐵𝑋𝑡 | = 4 and 𝑚 = 4

0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

0.4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

0.6

p-value

1 0.8

p-value

1 0.8

p-value

1 0.8

p-value

1 0.8

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

p-value

Figure 6: Relationship between time and 𝑝-values in Rome, Italy (returned by testing H0 in different intervals).

Time

threshold = 0.05

(e) |𝐵𝑋𝑡 | = 5 and 𝑚 = 5

Figure 7: Relationship between time and 𝑝-values in Porto, Portugal (returned by testing H0 in different intervals).

10

103

Rome Porto

2

101

Frequency

Frequency

103

Rome Porto 102

101

100

100

0

2

4

6

8

10

Prediction time (sec)

12 10-3

1

2

3

Markov blanket size

Figure 8: Markov blanket pre- Figure 9: Markov blanket diction time distribution. size distribution. Markov blanket sizes in both cities. From the figure, we observe that 99.8% and 100.0% of the predicted Markov blanket sizes are no larger than 2 in Rome and Porto respectively. This indicates that the distribution of most locations primarily depends on their previous two locations. Hence, the number of possible Markov blanket states remains constant as the road network expands, as the number of neighboring locations within a road network is generally limited and does not scale with the network size.

5.3

Utility Loss Evaluation

5.3.1 Utility loss measure. Given the task location 𝑥 task and the real (next) location 𝑥 ℓ , the utility loss caused by a perturbed location 𝑦𝑘 is given by |𝑝𝑎𝑡ℎ(𝑥 ℓ , 𝑥 task ) − 𝑝𝑎𝑡ℎ(𝑦𝑘 , 𝑥 task )|, where 𝑝𝑎𝑡ℎ(𝑥 ℓ , 𝑥 task ) (resp. 𝑝𝑎𝑡ℎ(𝑦𝑘 , 𝑥 task )) represents the path distance from 𝑥 ℓ (resp. 𝑦𝑘 ) to 𝑥 task . The data utility loss 𝑐 (𝑥𝑖 ,b),𝑦𝑘 is calculated by 𝑐 (𝑥𝑖 ,b),𝑦𝑘 =

∑︁ 𝑥 task ∈V

𝑝𝑥 task ·

∑︁

𝑝 (𝑥 ℓ ,b) · |𝑝𝑎𝑡ℎ (𝑥 ℓ , 𝑥 task ) − 𝑝𝑎𝑡ℎ (𝑦𝑘 , 𝑥 task ) | .

𝑥 ℓ ∈X

(34)

where 𝑝𝑥 task is the prior probability of the task being at location 𝑥 task and 𝑝 (𝑥 ℓ ,b) is the probability of real location being at 𝑥 ℓ given the current location 𝑥𝑖 and the context information b. Here, when computing the path distance a vehicle travels to reach its destination, we approximate both the vehicle’s location and the destination location as “nodes” within the road network, where V is the node set. Then, we employ the Dijkstra algorithm [7] to determine the shortest path distance from the vehicle’s location to the destination node.

Time complexity of utility loss measure: Given a task with the location 𝑥 task , we first build the shortest path tree rooted at 𝑥 task using Dijkstra’s algorithm [7], of which the time complexity is 𝑂 (|V | + |E |), where V and E are the node (location) set and edge set of the road network of the target city, respectively. Since there are |V | possible task locations, the time complexity of building the shortest path trees for possible task locations is 𝑂 (|V | 2 + |E ||V |). The shortest path tree can be used to calculate 𝑝𝑎𝑡ℎ(𝑥𝑖 , 𝑥 task ) and 𝑝𝑎𝑡ℎ(𝑦𝑘 , 𝑥 task ) for all pairs (𝑥𝑖 , 𝑦𝑘 ), with 𝑂 (|X||V |) (|X| ≤ |V |) subtraction operations to calculate 𝑐 (𝑥𝑖 ,b),𝑦𝑘 defined in Eq. (34). Considering that there are |X| different possible 𝑥𝑖 , |Y| different 𝑦𝑘 , and |B| different Markov blanket b, the time complexity of calculating all 𝑐 (𝑥𝑖 ,b),𝑦𝑘 is 𝑂 (|B||X| 2 |Y||V | + |V | 2 + |E ||V |). 5.3.2 Compared methods. In each dataset, we randomly sampled 500 trajectories, selecting one location within each trajectory to represent the target vehicles’ positions. For each vehicle, we placed 1 destination within the target region. We evaluate our method “LP+C-mDP” by comparing it with the following benchmarks, which are all based on mDP: (1) “LP” [35], which optimizes mDP using LP framework with the consideration of vehicles’ mobility in the road network. Notably, other works such as [30, 36] also fall into this category, as they both use an LP framework to optimize location perturbation. However, they differ in their approaches—[30] represents locations hierarchically, while [36] incorporates quality constraints into the optimization process. (2) “ExpMech” [29], where the perturbation probability of each secret record follows an exponential distribution. (3) “ConstOPTMech” or “ConstOPT ” [21], which integrates the exponential mechanism into the LP framework. (4) “LP+TrueMB” follows our LP+C-mDP framework but replaces the Markov blanket predicted by the learning-based MBI module with the true Markov blanket obtained via CI testing on the trajectory data. We use this benchmark as an oracle reference to quantify how blanket-prediction errors affect utility. Importantly, the MBI prediction errors do not change our privacy guarantee: C-mDP is enforced by constraints over the chosen secret domain and metric, independent of predictor accuracy, and the required distances are

34 32 30

Expected utility loss (m)

Expected utility loss (m)

36

LP+C-mDP LP+Markov LP+TrueMB LP ConstOPT ExpMech

28 26 24 22 20 18 0.5

1

1.5

0 (km-1)

(a) Rome, Italy

2

2.5

Computation time (sec)

50

40 38

Conference’17, July 2017, Washington, DC, USA

45 40 35 30

LP+C-mDP LP+Markov LP+TrueMB LP ConstOPT ExpMech

25 20 0.5

1

1.5

2

12 10 8 6 4

0

0.5

1

1.5

0 (km-1)

2.5

0 (km-1)

(b) Porto, Portugal

Rome Porto

2

2

2.5

Computation time (7 s)

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

1.2 1 0.8 0.6 0.4

Rome Porto

0.2 0

0.5

1

1.5

2

2.5

0 (km-1)

(a) Perturbation optimization (b) Perturbation record selection

Figure 10: Expected utility loss vs. privacy budget 𝜖.

Figure 11: Computation time of data perturbation.

computed exactly from the map metric by the user/device. Consequently, prediction errors primarily impact utility (and efficiency) by selecting less/more relevant context, rather than weakening the mechanism-level privacy bound on the released output. (5) “LP+Markov” removes the Markov blanket identification module (Section 4) and instead assumes a fixed-order Markov mobility model. Concretely, LP+Markov1 uses the first-order context 𝑋𝑡 −1 . We do not include higher-order Markov baselines because the optimization cost grows rapidly with the model order: optimizing 𝑞 (𝑥𝑡 ,𝑥𝑡 −1 ),𝑦 already requires O (|X| 2 |Y|) variables, whereas optimizing 𝑞 (𝑥𝑡 ,𝑥𝑡 −1 ,𝑥𝑡 −2 ),𝑦 (i.e., a second-order Markov model) increases this to O (|X| 3 |Y|), with a comparable blow-up in the number of constraints. In contrast, our Markov-blanket-based approach avoids committing to a fixed global order by selecting only the relevant past locations when needed. Notably, the privacy budget 𝜖 is a shared scalar across all guarantees, appearing
in the standard likelihood-ratio bound in the form exp 𝜖 ·𝑑 (·, ·) . However, the resulting indistinguishability is defined with respect to a particular secret domain and its associated distance metric. Context-free mechanisms (e.g., LP, ConstOPT, and ExpMech) enforce 𝜖-mDP on the single-location domain X using the base location metric 𝑑𝑥,𝑥 ′ . In contrast, context-aware mechanisms (including our C-mDP and the Markov-based variants) enforce the same 𝜖 on an augmented secret domain (e.g., X × V or its Markov-blanket reduction) under an extended metric 𝑑 (𝑥,v),(𝑥 ′ ,v′ ) that accounts for multiple (historical) locations. Thus, fixing 𝜖 keeps the privacy budget parameter consistent across mechanisms, while changing the secret domain/metric changes what is being protected; empirical comparisons at a fixed 𝜖 should therefore be interpreted as utility trade-offs under different protection targets (single-location secrecy versus context/trajectory-aware secrecy). The detailed description of the objective functions of the LPbased methods, LP, ConstOPTMech, and LP+Markov, is given in Appendix D. We applied the above five mDP methods to perturb the vehicles’ locations and recommended destinations based on their perturbed locations. We set 𝜂 = 5.0𝑘𝑚 by default.

(with the largest gaps observed in Porto under moderate-to-large 𝜖). Moreover, LP+C-mDP performs very close to LP+TrueMB, typically within 1%–2%, indicating that the C-mDP formulation effectively approximates the full Markov blanket dependency structure. In contrast, LP+Markov consistently incurs about 3%–8% higher utility loss than LP+C-mDP, reflecting the limitation of modeling vehicle mobility using only a first-order Markov assumption. The performance gain of LP+C-mDP over LP stems from its incorporation of context information within the Markov blanket, which enables a more accurate characterization of context-dependent utility loss during the optimization process. By contrast, ConstOPT and ExpMech rely (fully or partially) on exponential mechanisms that do not explicitly account for road-network constraints and mobility dependencies, leading to higher utility loss. Furthermore, LP+Markov assumes a first-order Markov chain and ignores additional preceding locations that are not conditionally independent of the next location, which explains its consistently higher utility loss compared to LP+C-mDP. Tradeoff between privacy and utility. In the mDP framework, the privacy budget 𝜖 represents the required privacy level. A lower 𝜖 indicates a higher privacy level, requiring more noise to be added to the protected data, which can degrade utility due to reduced data fidelity. As expected, a clear privacy–utility tradeoff is observed in both Fig. 10(a)(b). As the privacy budget 𝜖 increases, the utility loss of all mechanisms (LP+C-mDP, LP, ExpMech, LP+TrueMB, and LP+Markov) decreases. This trend arises because a larger 𝜖 relaxes the privacy constraints, enabling the mechanism to select perturbed locations that are closer to the true location. While this leads to improved utility by preserving higher location accuracy, it simultaneously weakens privacy protection, as the released data reveals more information about the original location.

5.3.3 Experimental results. We evaluate the expected utility loss of the six data perturbation methods by varying the privacy budget 𝜖 from 0.5 𝑘𝑚 −1 to 0.25 𝑘𝑚 −1 and present the results in Fig. 10(a)(b). The experimental results demonstrate the superior performance of LP+C-mDP in terms of utility loss across both the Rome and Porto datasets. Across all evaluated 𝜖 values, LP+C-mDP achieves approximately 13%–17% lower utility loss than LP, 25%–36% lower than ConstOPT, and more than 25%–50% lower than ExpMech

5.4

Computation Efficiency Evaluation

Finally, we evaluate the computational efficiency of perturbation matrix optimization and perturbed record selection. We use the MATLAB optimization toolbox linearprog to solve the LP problem formulated in Eq. (30)–(33). Fig. 11(a) reports the computation time (in seconds) for solving the LP with linearprog as a function of the privacy budget 𝜖 (km−1 ) on the Rome and Porto datasets. Overall, the LP solving time remains low and stable, ranging from ≈ 8.07 s to ≈ 11.53 s across all settings. Specifically, for Rome, the runtime across different privacy budget is approximately 8-12 seconds, with an average of ≈ 10.24 seconds. For Porto, the corresponding runtime is approximately

Conference’17, July 2017, Washington, DC, USA

8-10 seconds, with an average of ≈ 9.34 seconds. These results indicate that the LP-based perturbation matrix optimization is computationally efficient (on the order of ∼10 seconds per solve) and does not exhibit a sharp runtime increase as 𝜖 varies. Overall, the figure demonstrates that solving the perturbation matrix optimization problem via linearprog is computationally efficient and practically feasible, as the runtime remains stable and lightweight across all evaluated settings. Note that, both perturbation matrix and utility loss can be precomputed, indicating such computation time is acceptable. Given the perturbation perturbation matrix, we then measure the computation time for perturbed record selection and depict the results in Fig. 11(b). From the figure, we observe that the computation time doesn’t exceed 1.10 milliseconds, while the average computation time is 1.01 milliseconds, which is also acceptable for vehicle-based spatial crowdsourcing.

6

Related Works

mDP. mDP was originally introduced in the domain of location privacy, requiring “geo-indistinguishability” for each pair of nearby locations [4]. In this context, “neighboring records” are defined based on their Euclidean distance, diverging from the original DP classification, which relies on the Hamming distance of databases. Currently, mDP has been explored using various metric choices, including Haversine distance and Euclidean distance in geo-location data [30], as well as Hyperbolic distance [19] and Levenshtein distance [22] in text data. Considering the varied sensitivity of utility loss to perturbation in general distance metric spaces, a widely used paradigm of finding the optimal mDP is to formulate it as an LP problem [8], which, however, may suffer from the polynomial explosion of variables and constraints [21]. Recent efforts such as [28, 32, 34, 35] have enhanced the computational efficiency of LPbased methods by employing optimization decomposition. Another line of work applies exponential noise [12] or combines the predefined noise with LP [21, 33], which achieves higher computation efficiency but at the expense of compromising data utility. Context-aware data perturbation. Many research works have extended DP to context-aware data perturbation. A notable such framework is called Pufferfish privacy [23], which allows data protectors to define privacy for their own data-sharing demands by considering datasets’ background information. DP actually can be viewed as a specific instance of Pufferfish privacy when the correlation between secret records is not considered. Inspired by Pufferfish, He et al. [20] proposed the Blowfish privacy framework by allowing users to specify the secret records to protect. Following these frameworks, several other studies have focused on describing the dataset background information using various statistical models such as parameter-based descriptions of correlation [15, 27, 46], Gaussian correlation models [14, 44], and Markov chain models [37]. These related works differ from ours in two key aspects. Firstly, they primarily examine how context information (data correlation) affects DP, whereas our focus is on how context information influences utility loss caused by data perturbation. Secondly, they rely on the Hamming distance to define neighboring databases, as is typical in traditional DP, whereas we consider mDP, where the distance between secret records is defined within a general metric space. This

Trovato et al.

extension to a metric space in mDP introduces unique challenges, as it requires more precise noise control due to the finer-grained indistinguishability between secret data and the varying utility loss caused by noise in different directions and magnitudes. Spatiotemporal location privacy. Some recent studies address context-aware location privacy by analyzing the spatiotemporal correlations in mobile users’ reported locations, focusing either on data from a single user across multiple time points (e.g., trajectory data) [5, 11, 17, 24, 26, 43] or on data from multiple users [10, 25]. Many of these works assume that users’ movements follow a firstorder Markov process [17, 26], where each user’s current location depends on the previous location. For example, Liao et al. [26] applied a hierarchical Markov model to predict a user’s trajectory based on their visited places and observed temporal patterns. Our framework is distinct from these works as we discard the Markovian assumption, proposing a more general model that captures correlations in protected data. Our empirical study further reveals that vehicle mobility patterns may not strictly adhere to a first-order Markov process, with Markov blankets for locations showing strong dependence on environmental factors such as regional differences and time.

7

Discussion and Conclusion

In this paper, we proposed a new mDP framework, C-mDP, by considering the impact of context information on data perturbation. Considering the high computation load of C-mDP when solving it as an LP, we reduce its complexity by identifying the CI relationship between secret records and context variables. To illustrate practical applicability, we conduct a case study by applying C-mDP to protect vehicles’ location privacy. The experimental results demonstrate the superiority of C-mDP over the existing mDP methods. We identify several promising directions to further improve the proposed C-mDP framework. First, our current perturbation optimization assumes data utility depends on the distribution of secret data (Assumption 1). To address potential correlations in downstream data processing, we plan to remove this assumption and further explore CI relationships among secret records. Section C of the Appendix outlines how to adapt the C-mDP framework when this assumption is relaxed. Second, we aim to develop context-aware threat models where attackers use context data to narrow the search space of secret data, improving inference accuracy. As a countermeasure, we will constrain perturbed data within a range (e.g., identified by deep generative models) where it becomes difficult for attackers using context information to distinguish perturbed data from real data. Finally, our current evaluation uses public, de-identified trajectory data to estimate population-level mobility statistics (e.g., priors/transition tendencies and Markov blanket structure) and to compute the offline perturbation matrix Q. In practical deployments, however, such statistics (or auxiliary predictive models used to estimate them) may be learned from sensitive, non-public user data. An important direction for future work is therefore to privatize the offline mechanism-design pipeline itself, for example, by learning the required priors/transition statistics (or training the corresponding neural models) under differential privacy (e.g., by releasing DP-sanitized aggregates), and then composing that privacy loss with the output-privacy budget that governs the released

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

perturbed outputs. This extension would provide end-to-end privacy protection covering both offline model/parameter learning and online per-user perturbation.

8

Acknowledgements

The authors used ChatGPT 5.2 to revise the text in Sections 1–7 to correct typos, grammatical errors, and awkward phrasing.

References [1] 2019. Taxi Service Trajectory - Prediction Challenge, ECML PKDD 2015 Data Set. https://archive.ics.uci.edu/ml/datasets/Taxi+Service+Trajectory++Prediction+Challenge,+ECML+PKDD+2015. Accessed: 2019-07-22. [2] 2020. openstreetmap. https://www.openstreetmap.org/. Accessed: 2020-04-07. [3] 2024. PyTorch. https://pytorch.org/. Accessed in January 2024. [4] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. 2013. Geo-indistinguishability: Differential Privacy for Location-based Systems. In Proc. of ACM CCS. 901–914. [5] Qasim Ali Arain, Imran Memon, Zhongliang Deng, Muhammad Hammad Memon, Farman Ali Mangi, and Asma Zubedi. 2018. Location Monitoring Approach: Multiple Mix-Zones with Location Privacy Protection Based on Traffic Flow over Road Networks. Multimedia Tools Appl. 77, 5 (mar 2018), 5563–5607. [6] Alexis Bellot and Mihaela van der Schaar. 2019. Conditional Independence Testing Using Generative Adversarial Networks. Curran Associates Inc., Red Hook, NY, USA. [7] Harsh Bhasin. 2015. Algorithms: Design and Analysis. Oxford Univ Press. [8] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. 2014. Optimal GeoIndistinguishable Mechanisms for Location Privacy. In Proc. of ACM CCS. 251– 262. [9] Lorenzo Bracciale, Marco Bonola, Pierpaolo Loreti, Giuseppe Bianchi, Raul Amici, and Antonello Rabuffi. 2014. CRAWDAD dataset roma/taxi (v. 2014-07-17). Downloaded from https://crawdad.org/roma/taxi/20140717. doi:10.15783/C7QC7M [10] Y. Cao, Y. Xiao, L. Xiong, and L. Bai. 2019. PriSTE: From Location Privacy to Spatiotemporal Event Privacy. In Proc. of IEEE ICDE. 1606–1609. [11] Yang Cao, Masatoshi Yoshikawa, Yonghui Xiao, and Li Xiong. 2017. Quantifying Differential Privacy under Temporal Correlations. In Proc. of 2017 IEEE 33rd International Conference on Data Engineering (ICDE). 821–832. doi:10.1109/ICDE. 2017.132 [12] Ricardo Silva Carvalho, Theodore Vasiloudis, and Oluwaseyi Feyisetan. 2021. TEM: High Utility Metric Differential Privacy on Text. ArXiv abs/2107.07928 (2021). https://api.semanticscholar.org/CorpusID:236034456 [13] Konstantinos Chatzikokolakis, Miguel E. Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. 2013. Broadening the Scope of Differential Privacy Using Metrics. In Proc. of Privacy Enhancing Technologies, Emiliano De Cristofaro and Matthew Wright (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 82–102. [14] J. Chen, H. Ma, D. Zhao, and L. Liu. 2021. Correlated Differential Privacy Protection for Mobile Crowdsensing. IEEE Transactions on Big Data 7, 04 (oct 2021), 784–795. doi:10.1109/TBDATA.2017.2777862 [15] 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. doi:10.1007/s00778-013-0344-8 [16] Cynthia Dwork. 2006. Differential Privacy. In Proc. of Automata, Languages and Programming, Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1–12. [17] T. Emrich, H. Kriegel, N. Mamoulis, M. Renz, and A. Zufle. 2012. Querying Uncertain Spatio-Temporal Data. In Proc. of IEEE ICDE. 354–365. [18] K. Fawaz and K. G. Shin. 2014. Location Privacy Protection for Smartphone Users. In Proc. of ACM CCS (Scottsdale, Arizona, USA). ACM, New York, NY, USA, 239–250. doi:10.1145/2660267.2660270 [19] O. Feyisetan, T. Diethe, and T. Drake. 2019. Leveraging Hierarchical Representations for Preserving Privacy and Utility in Text. In 2019 IEEE International Conference on Data Mining (ICDM). IEEE Computer Society, Los Alamitos, CA, USA, 210–219. doi:10.1109/ICDM.2019.00031 [20] Xi He, Ashwin Machanavajjhala, and Bolin Ding. 2014. Blowfish Privacy: Tuning Privacy-Utility Trade-Offs Using Policies. In Proc. of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ’14). Association for Computing Machinery, New York, NY, USA, 1447–1458. doi:10.1145/2588555.2588581 [21] Jacob Imola, Shiva Kasiviswanathan, Stephen White, Abhinav Aggarwal, and Nathanael Teissier. 2022. Balancing utility and scalability in metric differential privacy. In Proc. of UAI 2022. https://www.amazon.science/publications/balancingutility-and-scalability-in-metric-differential-privacy [22] Austin Jones, Kevin J. Leahy, and Matthew T. Hale. 2018. Towards Differential Privacy for Symbolic Systems. 2019 American Control Conference (ACC) (2018), 372–377. https://api.semanticscholar.org/CorpusID:52811575

Conference’17, July 2017, Washington, DC, USA

[23] Daniel Kifer and Ashwin Machanavajjhala. 2012. A Rigorous and Customizable Framework for Privacy. In Proc. of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Scottsdale, Arizona, USA) (PODS ’12). Association for Computing Machinery, New York, NY, USA, 77–88. doi:10.1145/ 2213556.2213571 [24] Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, and W. Ma. 2008. Mining User Similarity Based on Location History. In Proc. of SIGSPATIAL. Article 34, 10 pages. [25] W. Li, H. Chen, W. Ku, and X. Qin. 2017. Scalable Spatiotemporal Crowdsourcing for Smart Cities Based on Particle Filtering. In Proc. of ACM SIGSPATIAL. [26] L. Liao, D. J. Patterson, D. Fox, and H. Kautz. 2007. Learning and inferring transportation routines. Artificial Intelligence 171, 5 (2007), 311 – 331. [27] Changchang Liu, Supriyo Chakraborty, and Prateek Mittal. 2016. Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples. In Proc. of Network and Distributed System Security Symposium. [28] Ruiyao Liu and Chenxi Qiu. 2025. PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based Approximation. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (Taipei, Taiwan) (CCS ’25). Association for Computing Machinery, New York, NY, USA, 1290–1304. doi:10.1145/3719027.3765042 [29] Frank McSherry and Kunal Talwar. 2007. Mechanism Design via Differential Privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). 94–103. doi:10.1109/FOCS.2007.66 [30] P. Pappachan, C. Qiu, A. Squicciarini, and V. Manjunath. 2023. User Customizable and Robust Geo-Indistinguishability for Location Privacy. In Proc. of International Conference on Extending Database Technology (EDBT). [31] Shaojie Qiao, Dayong Shen, Xiaoteng Wang, Nan Han, and William Zhu. 2015. A Self-Adaptive Parameter Selection Trajectory Prediction Approach via Hidden Markov Models. IEEE Transactions on Intelligent Transportation Systems 16, 1 (2015), 284–296. doi:10.1109/TITS.2014.2331758 [32] C. Qiu. 2024. Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition. In Proc. of 33rd International Joint Conference on Artificial Intelligence (IJCAI) 2024. Interpolation-Based Optimization for Enforcing lp[33] Chenxi Qiu. 2026. Norm Metric Differential Privacy in Continuous and Fine-Grained Domains. arXiv:2601.09946 [cs.LG] https://arxiv.org/abs/2601.09946 [34] C. Qiu, A. C. Squicciarini, Z. Li, C. Pang, and L. Yan. 2020. Time-Efficient GeoObfuscation to Protect Worker Location Privacy over Road Networks in Spatial Crowdsourcing. In Proc. of ACM CIKM 2024. [35] C. Qiu, A. C. Squicciarini, C. Pang, N. Wang, and B. Wu. 2020. Location Privacy Protection in Vehicle-Based Spatial Crowdsourcing via Geo-Indistinguishability. IEEE Transactions on Mobile Computing (2020), 1–1. doi:10.1109/TMC.2020. 3037911 [36] C. Qiu, S Yadav, Y. Ji, A. Squicciarini, R. Dantu, J. Zhao, and C. Xu. 2024. FineGrained Geo-Obfuscation to Protect Workers’ Location Privacy in Time-Sensitive Spatial Crowdsourcing. In Proc. of 27th International Conference on Extending Database Technology (EDBT). [37] C. Qiu, L. Yan, A. Squicciarini, J. Zhao, C. Xu, and P. Pappachan. 2022. TrafficAdaptor: An Adaptive Obfuscation Strategy for Vehicle Location Privacy Against Vehicle Traffic Flow Aware Attacks. In Proc. of ACM SIGSPATIAL. [38] Meyer Scetbon, Laurent Meunier, and Yaniv Romano. 2022. An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings. In Proceedings of the 39th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (Eds.). PMLR, 19328–19346. https: //proceedings.mlr.press/v162/scetbon22a.html [39] R. Sen, A. Suresh, K. Shanmugam, G. Alexandros Dimakis, and S. Shakkottai. 2017. Model-Powered Conditional Independence Test. In Advances in Neural Information Processing Systems, Vol. 30. [40] Daniel W. Stroock. 2010. Probability Theory: An Analytic View (2nd ed.). Cambridge University Press. [41] H. To, G. Ghinita, L. Fan, and C. Shahabi. 2017. Differentially Private Location Protection for Worker Datasets in Spatial Crowdsourcing. IEEE Transactions on Mobile Computing (2017), 934–949. [42] I. Tsamardinos, Constantin F. Aliferis, and Alexander R. Statnikov. 2003. Algorithms for Large Scale Markov Blanket Discovery. In The Florida AI Research Society. https://api.semanticscholar.org/CorpusID:1930258 [43] F. Xu, Z. Tu, Y. Li, P. Zhang, X. Fu, and D. Jin. 2017. Trajectory Recovery From Ash: User Privacy Is NOT Preserved in Aggregated Mobility Data. In Proc. of ACM WWW. 1241–1250. [44] Bin Yang, Issei Sato, and Hiroshi Nakagawa. 2015. Bayesian Differential Privacy on Correlated Data. In Proc. of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 747–762. doi:10.1145/2723372. 2747643 [45] L. Yu, L. Liu, and C. Pu. 2017. Dynamic Differential Location Privacy with Personalized Error Bounds. In Proc. of IEEE NDSS.

Conference’17, July 2017, Washington, DC, USA

Trovato et al.

[46] Tianqing Zhu, Ping Xiong, Gang Li, and Wanlei Zhou. 2015. Correlated Differential Privacy: Hiding Information in Non-IID Data Set. IEEE Transactions on Information Forensics and Security 10, 2 (2015), 229–242. doi:10.1109/TIFS.2014.2368363

and hence

Appendix A Math Notations

=

Table 3: Main notations and their descriptions. Symbol 𝑄 X Y V 𝑋 𝑉𝑋 𝐵𝑋 𝑋𝑡 𝑥𝑖 𝑦𝑘 𝜖 𝑑𝑥𝑖 ,𝑥 𝑗 Q L (Q) 𝑞𝑥𝑖 ,𝑦𝑘 𝑞 (𝑥𝑖 ,v),𝑦𝑘 𝑞 (𝑥𝑖 ,b),𝑦𝑘 𝑐 𝑥𝑖 ,𝑦𝑘

Description Perturbation function Secret data set (domain of the function 𝑄) Perturbed data set (range of the function 𝑄) Contextual information space Random variable of secret data Context variables of secret data 𝑋 Markov blanket of secret data 𝑋 (Case study) Random variable to represent the target vehicle’s location at time slot 𝑡 Secret record 𝑖 Perturbed record 𝑘 Privacy budget Distance between secret records 𝑥𝑖 and 𝑥 𝑗 Perturbation matrix Loss function of the perturbation matrix Q Probability of selecting 𝑦𝑘 as the perturbed data given the real record 𝑥𝑖 Probability of selecting 𝑦𝑘 as the perturbed data given the real record 𝑥𝑖 and the context data v Probability of selecting 𝑦𝑘 as the perturbed data given the real record 𝑥𝑖 and the Markov blanket b Data utility loss caused by the perturbed record 𝑦𝑘 when the real record is 𝑥𝑖

Now suppose the C-mDP constraints in Eq. (14) hold, then whenever 𝑞 (𝑥 𝑗 ,v′ ),𝑦 > 0, Eq. (14) implies ! 𝑞 (𝑥𝑖 ,v),𝑦 ln ≤ 𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) . (42) 𝑞 (𝑥 𝑗 ,v′ ),𝑦 Moreover, applying Eq. (14) again but with the pair swapped gives 𝑞 (𝑥 𝑗 ,v′ ),𝑦 ≤ 𝑒

Proposition 1. To satisfy the context-aware PL bound in Eq. (12), it is sufficient to enforce the C-mDP constraints · 𝑞 (𝑥 𝑗 ,v′ ),𝑦𝑘 ≤ 0, ∀𝑦𝑘 ∈ Y,

(35)

for each neighboring records 𝑥𝑖 , 𝑥 𝑗 ∈ X and all their possible context data v, v′ ∈ V. Proof. Let 𝑌 denote the released (perturbed) output, i.e., 𝑌 = 𝑄 (𝑋, 𝑉𝑋 ). For any (𝑥𝑖 , v) ∈ X × V and any 𝑦 ∈ Y, by Bayes’ rule,

= =

Pr [(𝑋, 𝑉 ) = (𝑥𝑖 , v) | 𝑌 = 𝑦] (36) Pr [(𝑋, 𝑉 ) = (𝑥𝑖 , v)] Pr [𝑌 = 𝑦 | (𝑋, 𝑉 ) = (𝑥𝑖 , v)] (37) Pr[𝑌 = 𝑦] 𝑝 (𝑥𝑖 ,v) · 𝑞 (𝑥𝑖 ,v),𝑦 . (38) Pr[𝑌 = 𝑦]

Hence, for any (𝑥𝑖 , v) and (𝑥 𝑗 , v′ ) with 𝑝 (𝑥 𝑗 ,v′ ) > 0 and any 𝑦 ∈ Y such that 𝑞 (𝑥 𝑗 ,v′ ),𝑦 > 0, we have 𝑝 (𝑥𝑖 , v) · 𝑞 (𝑥𝑖 ,v),𝑦 Pr [(𝑋, 𝑉 ) = (𝑥𝑖 , v) | 𝑌 = 𝑦]   = , ′ 𝑝 (𝑥 𝑗 , v′ ) · 𝑞 (𝑥 𝑗 ,v′ ),𝑦 Pr (𝑋, 𝑉 ) = (𝑥 𝑗 , v ) | 𝑌 = 𝑦

𝑞 (𝑥𝑖 ,v),𝑦

(43)

⇒

ln

𝑞 (𝑥𝑖 ,v),𝑦 ≥ −𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) . 𝑞 (𝑥 𝑗 ,v′ ),𝑦

(44)

Combining Eq. (42) and Eq. (44) yields, for all 𝑦 with 𝑞 (𝑥𝑖 ,v),𝑦 > 0 and 𝑞 (𝑥 𝑗 ,v′ ),𝑦 > 0, ! 𝑞 (𝑥𝑖 ,v),𝑦 ≤ 𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) . (45) ln 𝑞 (𝑥 𝑗 ,v′ ),𝑦 (If 𝑞 (𝑥 𝑗 ,v′ ),𝑦 = 0, then Eq. (14) forces 𝑞 (𝑥𝑖 ,v),𝑦 = 0 as well, so such 𝑦 does not affect the supremum.) Finally, substituting Eq. (45) into Eq. (41) and taking the supremum over 𝑦 ∈ Y gives
PL (𝑥𝑖 , v), (𝑥 𝑗 , v′ ) ≤ 𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) , which is exactly the context-aware PL bound in Eq. (12).

□

Proof of Proposition 2

Proposition 2. (PL guarantee) If a perturbation matrix Q follows the CD policy and satisfies the corresponding mDP constraints: 𝜖𝑑 ′ 𝑞 (𝑥𝑖 ,b),𝑦𝑘 − 𝑒 (𝑥𝑖 ,b),(𝑥 𝑗 ,b ) · 𝑞 (𝑥 𝑗 ,b′ ),𝑦𝑘 ≤ 0, ∀𝑥𝑖 , 𝑦𝑘 , b, b′ (46)

B Omitted Proofs B.1 Proof of Proposition 1

𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ )

𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ )

!

B.2

𝑞 (𝑥𝑖 ,v),𝑦𝑘 − 𝑒

!   Pr [(𝑋, 𝑉 ) = (𝑥𝑖 , v) | 𝑌 = 𝑦] 𝑝 (𝑥𝑖 , v)   − ln ln (40) 𝑝 (𝑥 𝑗 , v′ ) Pr (𝑋, 𝑉 ) = (𝑥 𝑗 , v′ ) | 𝑌 = 𝑦 ! 𝑞 (𝑥𝑖 ,v),𝑦 . (41) ln 𝑞 (𝑥 𝑗 ,v′ ),𝑦

where 𝑑 (𝑥𝑖 ,b),(𝑥 𝑗 ,b′ ) ≤ 𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) , it is sufficient for Q to achieve the bounded context-aware PL as defined in Eq. (12). Proof. Let 𝑌 denote the released output, i.e., 𝑌 = 𝑄 (𝑋, 𝑉𝑋 ). For any (𝑥, v) ∈ X × V and any 𝑦 ∈ Y, Bayes’ rule gives 𝑝 (𝑥,v) · 𝑞 (𝑥,v),𝑦 Pr [(𝑋, 𝑉 ) = (𝑥, v) | 𝑌 = 𝑦] = . (47) Pr[𝑌 = 𝑦] Hence, for any (𝑥𝑖 , v) and (𝑥 𝑗 , v′ ) with 𝑝 (𝑥 𝑗 , v′ ) > 0 and any 𝑦 with 𝑞 (𝑥 𝑗 ,v′ ),𝑦 > 0,     Pr[(𝑋, 𝑉 ) = (𝑥𝑖 , v) | 𝑌 = 𝑦] 𝑝 (𝑥𝑖 , v) ln − ln (48) Pr[(𝑋, 𝑉 ) = (𝑥 𝑗 , v′ ) | 𝑌 = 𝑦] 𝑝 (𝑥 𝑗 , v′ ) ! 𝑞 (𝑥𝑖 ,v),𝑦 = ln . (49) 𝑞 (𝑥 𝑗 ,v′ ),𝑦 Now assume Q follows the CD policy. Let b (resp., b′ ) denote the Markov blanket value associated with v (resp., v′ ), i.e., b = 𝜋 (v) and b′ = 𝜋 (v′ ) for the corresponding projection 𝜋 : V → B. By the CD policy, conditioning on (𝑋, b) makes the output independent of the remaining context, hence

(39) 𝑞 (𝑥,v),𝑦 = 𝑞 (𝑥,b),𝑦 ,

∀𝑥 ∈ X, ∀v ∈ V, ∀𝑦 ∈ Y,

(50)

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

Conference’17, July 2017, Washington, DC, USA

where b = 𝜋 (v). Since Q satisfies the reduced mDP constraints in Eq. (24), for all 𝑦 ∈ Y,
𝑞 (𝑥𝑖 ,b),𝑦 ≤ exp 𝜖𝑑 (𝑥𝑖 ,b),(𝑥 𝑗 ,b′ ) · 𝑞 (𝑥 𝑗 ,b′ ),𝑦 . (51) Moreover, applying Eq. (51) to the swapped pair (𝑥 𝑗 , b′ ) and (𝑥𝑖 , b) yields
𝑞 (𝑥 𝑗 ,b′ ),𝑦 ≤ exp 𝜖𝑑 (𝑥𝑖 ,b),(𝑥 𝑗 ,b′ ) · 𝑞 (𝑥𝑖 ,b),𝑦 , (52) and thus, for all 𝑦 with 𝑞 (𝑥𝑖 ,b),𝑦 > 0 and 𝑞 (𝑥 𝑗 ,b′ ),𝑦 > 0, ! 𝑞 (𝑥𝑖 ,b),𝑦 ln ≤ 𝜖𝑑 (𝑥𝑖 ,b),(𝑥 𝑗 ,b′ ) . 𝑞 (𝑥 𝑗 ,b′ ),𝑦

(53)

By the assumption 𝑑 (𝑥𝑖 ,b),(𝑥 𝑗 ,b′ ) ≤ 𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) , we further have ! 𝑞 (𝑥𝑖 ,v),𝑦 ≤ 𝜖𝑑 (𝑥𝑖 ,v),(𝑥 𝑗 ,v′ ) . (55) ln 𝑞 (𝑥 𝑗 ,v′ ),𝑦 Finally, substituting Eq. (55) into Eq. (49) and taking the supremum over 𝑦 ∈ Y yields the bounded context-aware posterior leakage in Eq. (12). Therefore, enforcing the reduced constraints in Eq. (24) under the CD policy is sufficient for Q to achieve the context-aware PL bound. □

Proof. We let sub B (v) represent the sub-vector of v consisting of entries in the Markov blanket space B. Based on marginalisation of probability [40], the relationship between 𝑞 (𝑥𝑖 ,b),𝑦𝑘 and 𝑞 (𝑥𝑖 ,v),𝑦𝑘 can be expressed through the following equation: ∑︁ 𝑞 (𝑥𝑖 ,v),𝑦𝑘 = 𝑞 (𝑥𝑖 ,b),𝑦𝑘 , ∀b, v. (57) subB (v)=b

Given that 𝑝𝑥𝑖 |c = 𝑝 (𝑥𝑖 ,b) and 𝑞𝑥𝑖 ,𝑦𝑘 |c = 𝑞 (𝑥𝑖 ,b),𝑦𝑘 , we can obtain that ∑︁ ∑︁ L (Q) = 𝑝 (𝑥𝑖 ,v) · 𝑐 (𝑥𝑖 ,v),𝑦𝑘 · 𝑞 (𝑥𝑖 ,v),𝑦𝑘 (58) v 𝑥𝑖 ,𝑦𝑘

= =

∑︁ ∑︁

∑︁

𝑝 (𝑥𝑖 ,b) · 𝑐 (𝑥𝑖 ,b),𝑦𝑘 · 𝑞 (𝑥𝑖 ,v),𝑦𝑘 (59)

b 𝑥𝑖 ,𝑦𝑘 subB (v)=b

𝑝 (𝑥𝑖 ,b) · 𝑐 (𝑥𝑖 ,b),𝑦𝑘 · 𝑞 (𝑥𝑖 ,b),𝑦𝑘 .

(60)

b 𝑥𝑖 ,𝑦𝑘

The proof is completed.

□

(63)

v: subB (v)=b

Í ∀𝑥𝑖 ∈ X, ∀b ∈ B, ∀𝑦𝑘 ∈ Y, where 𝑝 (𝑥𝑖 ,b) ≜ v: subB (v)=b 𝑝 (𝑥𝑖 ,v) . Refined C-mDP. Given {𝑞 ∗(𝑥𝑖 ,b),𝑦 } from the reduced problem, we 𝑘 solve the following LP to refine it: ∑︁ min 𝑝 (𝑥𝑖 ,v) · 𝑐 (𝑥𝑖 ,v),𝑦𝑘 · 𝑞 (𝑥𝑖 ,v),𝑦𝑘 (65) {𝑞 (𝑥𝑖 ,v),𝑦 } 𝑘

(𝑥𝑖 ,v),𝑦𝑘

s.t.

C-mDP constraints in Eq. (14) are satisfied, (66) ∑︁ 𝑝 (𝑥𝑖 ,v) · 𝑞 (𝑥𝑖 ,v),𝑦𝑘 = 𝑝 (𝑥𝑖 ,b) · 𝑞 ∗(𝑥𝑖 ,b),𝑦𝑘 , v: subB (v)=b

∀𝑥𝑖 , b, 𝑦𝑘 , ∑︁ 𝑞 (𝑥𝑖 ,v),𝑦𝑘 = 1,

Proposition 3. Given that Assumption 1 holds, the loss function L (Q) in Eq. (10) can be rewritten as the following reduced form: ∑︁ L (Q) = 𝑝 (𝑥𝑖 ,b) · 𝑐 (𝑥𝑖 ,b),𝑦𝑘 · 𝑞 (𝑥𝑖 ,b),𝑦𝑘 . (56) (𝑥𝑖 ,b),𝑦𝑘

𝑐 (𝑥𝑖 ,b),𝑦𝑘 .

In this section, we discuss how our approach can be adapted when Assumption 1 is removed, i.e., when 𝑐 (𝑥𝑖 ,v),𝑦𝑘 is not necessarily equal to 𝑐 (𝑥𝑖 ,b),𝑦𝑘 . We consider a two-step perturbation-optimization framework. In Step 1, we solve the reduced C-mDP under the CD policy and obtain an optimal mechanism {𝑞 ∗(𝑥𝑖 ,b),𝑦 } defined over (𝑥𝑖 , b). In Step 2, 𝑘 we refine {𝑞 ∗(𝑥𝑖 ,b),𝑦 } to a context-specific mechanism {𝑞 (𝑥𝑖 ,v),𝑦𝑘 } 𝑘 by preserving the induced marginals over b: ∑︁ 𝑝 (𝑥𝑖 ,v) · 𝑞 (𝑥𝑖 ,v),𝑦𝑘 = 𝑝 (𝑥𝑖 ,b) · 𝑞 ∗(𝑥𝑖 ,b),𝑦𝑘 , (64)

Proof of Proposition 3

∑︁ ∑︁

Discussion: When Assumption 1 Is Removed

In the main part, we focus on the case where the data utility loss depends only on the (conditional) distributions of the secret and perturbed data (Assumption 1). In particular, letting b = sub B (v) denote the restriction of v to the Markov-blanket space B, Assumption 1 implies that
𝑐 (𝑥𝑖 ,v),𝑦𝑘 = ℎ 𝑝 (𝑥𝑖 ,v) , 𝑞 (𝑥𝑖 ,v),𝑦𝑘 ; 𝜽 (61)
= ℎ 𝑝 (𝑥𝑖 ,b) , 𝑞 (𝑥𝑖 ,b),𝑦𝑘 ; 𝜽 (62) ≜

(If 𝑞 (𝑥 𝑗 ,b′ ),𝑦 = 0, Eq. (51) forces 𝑞 (𝑥𝑖 ,b),𝑦 = 0 as well, so such 𝑦 does not affect the supremum in the PL definition.) Combining Eq. (50) and Eq. (53) gives ! ! 𝑞 (𝑥𝑖 ,b),𝑦 𝑞 (𝑥𝑖 ,v),𝑦 ln = ln ≤ 𝜖𝑑 (𝑥𝑖 ,b),(𝑥 𝑗 ,b′ ) . (54) 𝑞 (𝑥 𝑗 ,v′ ),𝑦 𝑞 (𝑥 𝑗 ,b′ ),𝑦

B.3

C

(67) ∀(𝑥𝑖 , v),

(68)

∀(𝑥𝑖 , v), 𝑦𝑘 .

(69)

𝑦𝑘 ∈ Y

0 ≤ 𝑞 (𝑥𝑖 ,v),𝑦𝑘 ≤ 1,

Proposition 4. Let L ∗ be the optimal objective value of the original C-mDP problem (Eqs. (15)–(18)). Let L ref be the optimal objective value of the refined problem (Eqs. (65)–(67)). Then L ref ≥ L ∗ , i.e., the refined problem yields an upper bound on the optimal loss of the original C-mDP. Proof. The refined problem adds the marginal-preservation constraints in Eq. (67) to the original C-mDP constraints (and keeps the same simplex constraints). Therefore, any feasible solution to the refined problem is feasible for the original problem, i.e., the feasible set of the refined problem is a subset of that of the original problem. Since both problems minimize the same type of linear objective over their respective feasible sets, restricting the feasible set cannot decrease the optimal value. Hence L ref ≥ L ∗ . □

D

Definition of Objective Function L (Q) in Benchmarks

By considering the delay in receiving the recommended destination from the server, when estimating the actual travel cost 𝑐 (𝑥𝑖 |v, 𝑥 task ), we consider 𝑥𝑖 as the vehicle’s location in the subsequent time slot, rather than the current location. This requires the vehicle to predict

Conference’17, July 2017, Washington, DC, USA

Trovato et al.

the distribution of the next location when applying the utilitypreserving perturbation methods. Specifically, ⊲ (1) “LP” [35] and (3) “ConstOPT ” [21], as context-free perturbation methods, predict the next location using the prior distribution of the vehicles 𝑝𝑥𝑖 . Hence, their estimated utility loss functions LLP (Q) and LConstOPT (Q) are given by ∑︁ L̂LP (Q) = L̂ConstOPT (Q) = 𝑝𝑥𝑖 · 𝑐 𝑥𝑖 ,𝑦𝑘 · 𝑞𝑥𝑖 ,𝑦𝑘 (70) 𝑥𝑖 ,𝑦𝑘

(a) Rome

⊲ (4) “LP+Markov” assumes that the vehicle’s mobility follows a first-order Markov process. Given its current location 𝑥𝑡 , LP+Markov estimates the probability distribution of the next location as 𝑝𝑥𝑖 |𝑥𝑡 , which is the estimated transition probability from 𝑥𝑡 to 𝑥𝑖 of the Markov chain. In this case, its utility loss function L̂LP+Markov (Q) is estimated by ∑︁ ∑︁ L̂LP+Markov (Q) = 𝑝 (𝑥𝑖 ,𝑥𝑡 ) · 𝑐 (𝑥𝑖 ,𝑥𝑡 ),𝑦𝑘 · 𝑞 (𝑥𝑖 ,𝑥𝑡 ),𝑦𝑘 (71)

(b) Porto

Figure 12: PDF of neighbor distance.

𝑥𝑡 𝑥𝑖 ,𝑦𝑘

⊲ Our method “LP+C-mDP” uses the Markov Blanket b and the corresponding transition probability 𝑝 (𝑥𝑖 ,b) to predict the next location. Accordingly, the utility loss function is estimated by ∑︁ ∑︁ L̂LP+CmDP (Q) = 𝑝 (𝑥𝑖 ,b) · 𝑐 (𝑥𝑖 ,b),𝑦𝑘 · 𝑞 (𝑥𝑖 ,b),𝑦𝑘 (72)

(a) Rome

(b) Porto

Figure 13: Ratio of points with count≥threshold vs. Neighbor counts (radius=100m).

b 𝑥𝑖 ,𝑦𝑘

E

Supplementary Experimental Details and Analyses E.1 MBI Training Configuration and Platform We use Binary Cross-Entropy (BCE) loss with mean reduction and Adam with learning rate 10−5 and batch size 128. We apply early stopping if there is no validation improvement for 400 epochs. Experiments are conducted on a machine with an Intel Core i9-13900F CPU (24 cores, 2.00 -5.60 GHz), 32 GB DDR5 memory (4800 MHz), and an NVIDIA GeForce RTX 4090 GPU (24 GB GDDR6X VRAM). The training durations on Porto and Rome are 2730.0 s and 492.4 s, respectively.

E.2

Population-level Training vs. Per-vehicle Evaluation (with Overlap)

In our experimental pipeline, we use a large city-scale trajectory corpus (e.g., about 330k trajectories in Porto) to train the Markov blanket identification (MBI) module, and we use a smaller subset (500 trajectories) to evaluate the proposed perturbation mechanism and report utility/privacy results. Since the evaluation subset is sampled from the same corpus, it may overlap with trajectories used during MBI training. We view the 330k trajectories as capturing population-level mobility regularities of a city. Specifically, the CI-testing outputs and the learned feature-based predictor model how dependency strength (and thus Markov-blanket size) varies with coarse features such as speed, region, and time-of-day. This component is best interpreted as estimating a global statistical structure (a city-level prior), rather than modeling any particular vehicle. In contrast, the 500 trajectories are used to evaluate the perturbation mechanism on specific vehicles and measure the utility/privacy performance of the released outputs. Even with overlap, the MBI

(a) Rome

(b) Porto

Figure 14: Distribution of per-point mean-50NN distance.

module is used only to provide a city-level prior driven by aggregate regularities, while our formal privacy budget 𝜖 is defined for the online release 𝑌 = 𝑄 (𝑋, 𝑉𝑋 ). Intuitively, because the MBI module is trained to capture coarse, city-level patterns from large-scale data, it is not used as a vehicle-specific descriptor in our evaluation.

E.3

Neighborhood-Density Analysis

We also conduct a neighborhood-density analysis. Fig. 12, 13, 14 indicate that both Rome and Porto are highly dense location domains. In Fig. 12, the PDF of neighbor distances is concentrated near zero and decays rapidly, approaching zero around 20 meters, showing that most neighbors lie within a short distance. Fig. 13 shows that each location point has a large number of nearby candidates within a 100 m radius: 97.8%/95.7% of points (Rome/Porto) have at least 100 neighbors, 91.6%/89.1% have at least 500 neighbors, and 85.8%/84.0% have at least 1000 neighbors. Fig. 14 further shows that these neighbors are spatially close: the mean distance to the 50 nearest neighbors is at most 100 m for 99.5% of points in Rome and 98.1% in Porto (and at most 50 m for 98.6% and 96.8%, respectively).

Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

Overall, the results confirm that most location points have sufficiently dense local neighborhoods, which ensures that the mDPbased location privacy mechanism can be applied with an adequate set of nearby candidate locations.

Conference’17, July 2017, Washington, DC, USA