TraCS : Trajectory Collection in Continuous Space under Local Differential Privacy
Ye Zheng, Yidan Hu · 2024
Read TraCS : Trajectory Collection in Continuous Space under Local Differential Privacy by Ye Zheng, Yidan Hu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00620.txt.
Introduction
Ye Zheng and Yidan Hu collect movement trajectories without ever seeing anyone's true path, in a 2024 paper. Location traces expose routines and haunts, so collectors increasingly promise local differential privacy: scramble on the device, before upload.
Older methods force locations onto a grid, coupling privacy to grid size. Real traces, from drones to wearables, live in continuous space. The authors propose two scramblers: one jitters direction and distance, the other jitters the coordinates directly. Both analyze cleanly and run in constant time per point. Rounded back to a grid, they beat state-of-the-art methods on utility. Privacy guarantees no longer depend on how many places exist.
Catalog record
| CREATOR | Ye Zheng, Yidan Hu |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-00620
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
TraCS : Trajectory Collection in Continuous Space under Local Differential Privacy Ye Zheng, Yidan Hu Abstract . Trajectory collection is fundamental for location-based services but often involves sensitive information, such as a user’s daily routine, raising privacy concerns. Local differential privacy (LDP) provides provable privacy guarantees for users, even when the data collector is untrusted. Existing trajectory collection methods ensure LDP only for discrete location spaces, where the number of locations affects their privacy guarantees and trajectory utility. Moreover, the location space is often naturally continuous, such as in flying and sailing trajectories, making these methods unsuitable. This paper proposes two trajectory collection methods that ensure LDP for continuous spaces: TraCS-D , which perturbs the direction and distance of locations, and TraCS-C , which perturbs the Cartesian coordinates of locations. Both methods are theoretically and experimentally analyzed for trajectory utility. TraCS can also be applied to discrete spaces by rounding perturbed locations to the nearest discrete points. It is independent of the number of locations and has only Θ ( 1 ) \Theta(1) time complexity in each perturbation generation. Evaluation results on discrete location spaces validate this advantage and show that TraCS outperforms state-of-the-art methods with improved trajectory utility, especially for large privacy parameters. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/ZhengYeah/TraCS . 1. Introduction A trajectory is a sequence of locations that describes movement over time. Users’ trajectory data serves as a fundamental data source for location-based applications, such as navigation and route planning. However, the direct collection of trajectory data from users raises significant privacy concerns, particularly given the growing privacy expectations of users and stringent regulations ( gdp 2016 ; Krumm 2009 ) . Anonymization techniques, such as k -anonymity ( Sweeney 2002 ; Li et al. 2007 ) , have been shown to be insufficient for protecting trajectory privacy ( Chen et al. 2011 ) . Therefore, stronger privacy guarantees are needed for such data. Local differential privacy (LDP) provides a provable worst-case privacy guarantee by requiring the hardness of distinguishing the presence of a user’s data from any released data. The privacy level of an LDP mechanism is quantified by its privacy parameter \varepsilon , which also implies the extent of data perturbation. Through LDP, users can release their perturbed trajectory data to an untrusted data collector while still benefiting from the location-based services provided by the collector. Existing LDP methods for trajectory collection are designed for discrete spaces. They either rely on properly splitting the entire location space into grids ( Du et al. 2023 ) or assume the location space consists of a set of labeled locations (a.k.a. points of interest) ( Cunningham et al. 2021b ; Zhang et al. 2023 ) . These methods’ privacy guarantees are w.r.t. their corresponding discretized sets, and their efficacy depends on the size of these sets. Improper discretization leads to a loss of privacy guarantees and reduced trajectory utility. Moreover, labeled locations are not always available, especially in continuous spaces such as those encountered in flying and sailing trajectories. Therefore, it is necessary to design effective trajectory collection methods for continuous spaces. However, designing such methods is challenging due to the following reasons: (i) they must guarantee LDP w.r.t. each location in the continuous space; (ii) despite the rigorous privacy guarantee, they must still provide sufficient trajectory utility. This paper proposes two LDP methods for trajectory collection in continuous spaces. The main insight is to decompose the 2 D continuous space into 1 D subspaces and design mechanisms for each subspace. Our mechanisms leverage the concept of piecewise-based mechanisms ( Wang et al. 2019 ; Li et al. 2020 ) for 1 D bounded numerical domains. Based on two different decompositions of the continuous space, we propose two methods, TraCS-D and TraCS-C . TraCS-D treats the continuous space as the composition of a direction space and a distance space. We design a novel direction perturbation mechanism to ensure LDP for the direction space. Combined with a redesigned piecewise-based mechanism on the distance space, TraCS-D ensures LDP for the continuous 2 D space. TraCS-C treats the continuous space as the Cartesian product of two distance spaces. Each location has a 2 D Cartesian coordinate representation, and TraCS-C perturbs these coordinates. Our methods can also be applied to discrete spaces by rounding the perturbed location to the nearest discrete points. Compared with existing methods based on the Exponential mechanism ( Cunningham et al. 2021b ; Zhang et al. 2023 ) , our methods are not affected by the number of locations in the location space and cost only \Theta(1) time in each perturbation generation. Specifically, our contributions are as follows: • To the best of our knowledge, this is the first work to provide trajectory collection methods for continuous space under LDP. We propose TraCS-D and TraCS-C for this purpose. These methods introduce novel location perturbation mechanisms that exploit the direction information and coordinate information of trajectories in continuous spaces. We theoretically and experimentally analyze their trajectory utility. • Our methods TraCS can also be applied to discrete spaces. Compared with existing methods for discrete spaces, TraCS have significantly lower computation complexity in generating perturbed locations. Experimental results on the discrete location spaces validate the efficiency of TraCS , and also show that it outperforms the state-of-the-art methods with enhanced trajectory utility, particularly for large privacy parameters. 2. Preliminaries This section formulates the problem, introduces LDP, and reviews existing trajectory collection methods. 2.1. Problem Formulation A typical trajectory collection schema consists of a set of trajectories from users and one collector. Each trajectory \mathcal{T} is a sequence of locations \mathcal{T}=\{\tau_{1},\tau_{2},\dots,\tau_{n}\} , where \tau_{i}\in\mathcal{S} and \mathcal{S}\subset\mathbb{R}^{2} is a continuous and bounded domain. The collector needs to collect these trajectories to provide location-based services. However, the collector is untrusted and may act as an adversary attempting to infer users’ private data. Therefore, releasing the private trajectories to the collector pose a privacy risk. To protect privacy, users perturb their trajectories using a privacy mechanism \mathcal{M}:\mathcal{S}\to Range(\mathcal{M}) , and then send the perturbed trajectories \mathcal{T}^{\prime}=\{\tau_{1}^{\prime},\tau_{2}^{\prime},\dots,\tau_{n}^{\prime}\} to the collector. We aim to design a mechanism \mathcal{M} that satisfies \varepsilon -LDP, providing a provable privacy guarantee for the private trajectories. Additionally, \mathcal{M} should ensure the utility of the perturbed trajectories and incur limited computational cost for real-time applications. 2.2. Local Differential Privacy Definition 2.1 ( \varepsilon -LDP ( Duchi et al. 2013 ) ). A perturbation mechanism \mathcal{M}:\mathcal{X}\to Range(\mathcal{M}) satisfies \varepsilon -LDP, iff for two arbitrary input x_{1} and x_{2} , the probability ratio of outputting the same y is bounded: \forall x_{1},x_{2}\in\mathcal{X},\forall y\in Range(\mathcal{M}):\frac{\Pr[\mathcal{M}(x_{1})=y]}{\Pr[\mathcal{M}(x_{2})=y]}\leq\exp(\varepsilon). If \mathcal{M}(x) is continuous, the probability \Pr[\cdot] is replaced by probability density function ( pdf ). Intuitively, Definition 2.1 represents the difficulty of distinguishing