💻 computer science

TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy

This paper addresses the limitations of existing discrete-space methods by proposing TraCS, a novel framework for collecting trajectory data under Local Differential Privacy in continuous spaces that offers privacy and utility guarantees independent of the location space size while outperforming state-of-the-art methods.

Original authors: Ye Zheng, Yidan Hu

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ye Zheng, Yidan Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a city, and every few minutes, your phone takes a picture of exactly where you are. This creates a "trajectory"—a digital breadcrumb trail of your daily life. This data is gold for companies making maps, traffic apps, or fitness trackers. But there's a catch: if someone steals this trail, they can figure out where you sleep, where you work, and even your medical habits.

To protect you, we use a privacy shield called Local Differential Privacy (LDP). Think of this as a "privacy fog" that you apply to your location before you send it to the company. The company sees a blurry version of your path, but not the exact one.

The Problem: The "Pixelated Map" Trap

Most existing privacy tools treat the world like a giant Minecraft map. They force your smooth, continuous movement into a grid of tiny squares (discrete locations).

The Issue: If your city is huge, the grid has millions of squares. To keep you safe, the privacy tool has to add so much "fog" (noise) that your path becomes a useless, wandering mess.
The Bottleneck: It's like trying to find a specific house in a city of a million houses by guessing randomly. The more houses there are, the harder it is to guess correctly, and the more you have to distort the answer to stay private.

The Solution: TraCS (Trajectory Collection in Continuous Space)

This paper introduces TraCS, a new way to add privacy fog that works on the real, smooth map (continuous space) instead of forcing it into a grid first.

Think of it like this:

Old Way (Discrete): You are at a specific street corner. The privacy tool asks, "Which of these 10,000 corners are you at?" and then randomly picks a different one to confuse the spy.
TraCS Way (Continuous): You are at a specific point on a smooth road. The privacy tool doesn't ask "Which square?" Instead, it simply says, "I'm going to move your location a little bit to the left and a little bit forward," based on a secret mathematical rule.

How TraCS Works: Two New Tools

The authors created two different "fog machines" to handle this smooth space:

1. TraCS-D: The "Compass and Ruler" Method

Imagine you are giving directions to a friend. Instead of saying "I am at 5th and Main," you say, "I am 30 degrees North-East and 500 meters away from the park."

The Trick: TraCS-D breaks your location into two simple parts: Direction (which way you are facing) and Distance (how far you are).
The Magic: It adds a tiny bit of "noise" to the angle of your compass and a tiny bit of "noise" to the length of your ruler. Because it treats direction and distance separately, it can add just enough fog to hide you without making the path look like a crazy scribble.
Analogy: It's like telling a lie about your direction ("I'm heading slightly more East than I really am") and your distance ("I'm a bit closer than I really am") rather than pretending you are in a completely different city.

2. TraCS-C: The "Graph Paper" Method

Imagine a giant piece of graph paper. Your location is just an X and a Y coordinate.

The Trick: TraCS-C simply takes your X coordinate and adds a little fuzz to it, then takes your Y coordinate and adds a little fuzz to that.
The Magic: It's like taking a photo and blurring it slightly horizontally and vertically. It's very fast and simple because it doesn't need to calculate angles or compass directions.

Why is TraCS a Game Changer?

1. It Doesn't Care How Big the City Is
In the old "Minecraft" methods, if you doubled the size of the city (added more grid squares), the privacy tool got much worse. With TraCS, the size of the city doesn't matter. Whether you are in a small town or a massive metropolis, the "fog" works the same way. It's like having a flashlight that stays bright whether you are in a closet or a stadium.

2. It's Lightning Fast
The old methods had to check millions of possibilities to decide where to put the "fog." TraCS just does a quick math calculation.

Analogy: The old way is like a librarian searching through a million books to find one. TraCS is like a librarian who knows exactly which shelf the book is on and grabs it instantly.
Result: TraCS is 100 times faster than the best existing methods. This means it can run on your phone in real-time without draining your battery.

3. It Works Everywhere (Even on the Grid)
Even if you do want to use the old "Minecraft" grid system, TraCS can still help. It calculates the smooth location first, then just snaps it to the nearest grid square. Because the math was done on the smooth space, the result is still much more accurate and private than if you had done the math on the grid in the first place.

The Bottom Line

TraCS is like upgrading from a pixelated, blurry map to a high-definition, smooth GPS that respects your privacy. It allows us to collect movement data to improve our cities and services without forcing users to sacrifice their anonymity or their phone's battery life. It proves that you don't need to chop the world into tiny squares to keep it safe; you can protect the smooth, real world just as well.

1. Problem Statement

Trajectory data is vital for location-based services but reveals sensitive user information (routines, activities). While Local Differential Privacy (LDP) offers strong privacy guarantees even against untrusted data collectors, existing LDP trajectory collection methods face significant limitations:

Discrete Space Constraint: Current methods (e.g., NGram, L-SRR, ATP) operate on discrete location spaces (grids or Points of Interest).
Scalability Issues: Discrete methods often rely on the Exponential Mechanism, which incurs linear time complexity ( $\Theta(m)$ ) relative to the number of candidate locations $m$ . This becomes computationally prohibitive for large-scale or fine-grained spaces.
Privacy-Utility Trade-off: In discrete spaces, privacy guarantees are tied to the size of the location set. A larger set weakens effective privacy or requires excessive noise, degrading utility.
Inapplicability to Continuous Data: Many real-world applications (e.g., flying drones, wearable sensors, sailing) generate data in continuous spaces (real-valued coordinates). Discretizing these spaces introduces arbitrary granularity choices that negatively impact both privacy and utility.

Goal: Develop LDP mechanisms that operate natively in continuous 2D spaces, ensuring rigorous privacy, high utility, and constant-time ( $\Theta(1)$ ) efficiency per location, independent of the space size.

2. Methodology: TraCS

The authors propose TraCS (Trajectory Collection in Continuous Space), which decomposes the 2D continuous space into 1D subspaces to apply optimized piecewise-based perturbation mechanisms. They introduce two variants based on different geometric decompositions:

A. TraCS-D (Direction-Distance Decomposition)

Concept: Represents a location relative to a reference point using Direction ( $\varphi$ ) and Distance ( $r$ ).
Mechanism:
1. Direction Perturbation ( $M^\circ$ ): Perturbs the angle $\varphi \in [0, 2\pi)$ . Since the domain is circular, standard Laplace noise is unsuitable. The authors adapt a piecewise-based mechanism (inspired by OGPM) specifically for circular domains. It defines a "dominant sector" centered on the true direction with high probability, where the sector width dynamically shrinks as the privacy parameter $\varepsilon$ increases.
2. Distance Perturbation ( $M^-$ ): Perturbs the normalized distance $r \in [0, 1)$ . Uses a piecewise-based mechanism for bounded linear domains.
3. Composition: By the Sequential Composition Theorem, combining these two mechanisms ensures $\varepsilon$ -LDP for the 2D location.
Workflow: Iterates through the trajectory, perturbing the direction and distance from the previously perturbed location to the next sensitive location.

B. TraCS-C (Cartesian Decomposition)

Concept: Represents the location space as the Cartesian product of two independent distance spaces ( $D_a$ and $D_b$ ) relative to a fixed origin (e.g., bottom-left corner of the bounding box).
Mechanism:
1. Coordinate Perturbation: Treats the longitude and latitude (or $x, y$ coordinates) as two independent 1D bounded domains.
2. Process: Normalizes coordinates to $[0, 1)$ , applies the piecewise-based mechanism $M^-$ to each coordinate independently (splitting $\varepsilon$ as $\varepsilon/2$ for each), and then de-normalizes back to the original space.
Advantage: Simpler implementation as it avoids the circular domain complexity of TraCS-D.

C. Application to Discrete Spaces

TraCS can be applied to discrete spaces by rounding the perturbed continuous coordinates to the nearest discrete point (grid cell or POI).

Privacy: The LDP guarantee is established in the continuous domain; rounding is a post-processing step that does not weaken privacy.
Efficiency: The complexity remains $\Theta(1)$ per location, regardless of the number of discrete points, unlike Exponential mechanism-based methods.

3. Key Contributions

First Pure LDP for Continuous Trajectories: This is the first work to develop trajectory collection methods specifically for continuous spaces under pure LDP, avoiding the pitfalls of discretization.
Novel Decomposition Strategies:
- TraCS-D: Introduces a direction-distance perturbation scheme with a specialized circular-domain mechanism that eliminates fixed-sector errors inherent in naive $k$ -RR extensions.
- TraCS-C: Proposes a Cartesian coordinate perturbation scheme that is computationally efficient and easy to implement.
Theoretical Guarantees:
- Proves that both methods satisfy $\varepsilon$ -LDP for the entire trajectory.
- Demonstrates that Mean Square Error (MSE) converges to zero exponentially with $\varepsilon$ .
- Establishes $\Theta(1)$ time complexity per location, making it scalable to massive location sets.
Versatility: The methods work natively in continuous space and can be seamlessly adapted to discrete spaces via rounding, outperforming state-of-the-art discrete methods in both utility and speed.

4. Experimental Results

The authors evaluated TraCS on both synthetic and real-world datasets (Tokyo and Chicago) against baselines like NGram, L-SRR, ATP, and a Strawman approach (naive $k$ -RR + uniform sampling).

Utility (Accuracy):
- Continuous Space: TraCS significantly outperforms the Strawman approach and the Planar Laplace mechanism, especially as $\varepsilon$ increases. TraCS-C generally yields lower Average Error (AE) than TraCS-D for random trajectories in rectangular spaces.
- Discrete Space: TraCS outperforms NGram, L-SRR, and ATP in trajectory utility (measured by AE, Range Query Preservation, and Hotspot Preservation), particularly when $\varepsilon$ is large.
Efficiency (Time Cost):
- TraCS is drastically faster. On the TKY dataset, TraCS-D and TraCS-C required less than 1% of the time cost of L-SRR and less than 0.05% of the time cost of NGram and ATP.
- This is because TraCS avoids the $\Theta(m)$ sampling cost of the Exponential mechanism.
Scalability: Performance remains stable as the number of discrete locations ( $m$ ) increases, whereas discrete methods degrade significantly.

5. Significance

Paradigm Shift: TraCS shifts the focus from discretizing continuous data to operating directly in continuous space, resolving the inherent trade-offs between grid size, privacy, and utility.
Real-World Applicability: It enables privacy-preserving collection for applications that naturally generate continuous data (e.g., autonomous vehicles, drones, IoT sensors) without forcing arbitrary discretization.
Scalability: The $\Theta(1)$ complexity makes TraCS the first viable LDP solution for high-resolution, large-scale trajectory data collection, overcoming the computational bottlenecks of previous state-of-the-art methods.
Dual Utility: It serves as a superior method for both continuous applications and discrete applications (via rounding), offering a unified, efficient, and high-utility framework for trajectory privacy.