Spatio-temporal Trajectory Dataset Privacy Based on Network Traffic Control

Qilong Han, Qianqian Chen, Kejia Zhang, Xiaojiang Du, Nadra GuizaniarXiv 2018 · arXiv

Abstract

Spatio-temporal trajectory datasets are vital for network traffic analysis and resource optimization but pose significant privacy risks. Differential Privacy (DP) is the standard for protection, yet its application to high-dimensional prefix trees often results in excessive noise that destroys data utility. This paper introduces the Aggregation Prefix Tree Based (APTB) algorithm, which mitigates this "noise explosion" through node aggregation and a dynamic privacy budget allocation strategy. By grouping similar nodes and optimizing budget distribution based on tree depth, APTB enhances the signal-to-noise ratio, providing a more accurate and logically consistent dataset for research purposes.

Introduction: The Privacy-Utility Trade-off

Sharing location data is a double-edged sword. While researchers require trajectory data to predict network traffic bursts and optimize resource allocation, this information contains sensitive personal details that can reveal a user’s home address or lifestyle. The gold standard for protecting such data is Differential Privacy (DP), which adds mathematical noise to datasets to mask individual contributions.

However, spatio-temporal data (location and time) is inherently high-dimensional and sparse. When represented as a "prefix tree"—a common structure for trajectory data—the resulting tree becomes massive. Standard DP techniques add noise to every single node. In a deep, sparse tree, this noise quickly accumulates, drowning out the actual useful data. This paper proposes the APTB algorithm to bridge the gap between privacy and data utility.

The Prefix Tree Challenge

A prefix tree organizes trajectories by their common starting sequences. Each node represents a location at a specific time step, and the value in the node typically represents the count of trajectories passing through that point.

Figure 1: A standard prefix tree representation of trajectory data, showing how individual paths are aggregated into a hierarchical structure.

The primary challenge with this structure in a DP context is that as the tree grows deeper, the number of nodes increases exponentially. Adding noise to every node leads to a "noise explosion," where the cumulative error makes the data unusable for mining tasks.

The APTB Methodology

The authors propose the APTB (Aggregation Prefix Tree Based) algorithm to manage the prefix tree structure more efficiently. Its core innovation lies in how it handles noise injection and budget management.

1. Node Aggregation & Reconstruction

Instead of adding noise to every individual node, APTB groups nodes with similar count values into "coarse nodes." It uses the Exponential Mechanism to select neighboring nodes for merging, ensuring the selection process itself does not leak privacy. This significantly reduces the total number of noise injection points.

2. Dynamic Privacy Budget Allocation

Standard methods often split the privacy budget (epsilon) evenly across tree levels. APTB introduces a strategy based on a node’s theoretical maximum expansion (maxExpand). Nodes likely to lead to deeper subtrees receive a smaller portion of the budget, while nodes near the "leaves" receive more, optimizing the signal-to-noise ratio where it matters most.

Figure 2: The APTB prefix tree structure illustrating the dynamic allocation of the privacy budget (epsilon) and the resulting noisy counts across different levels.

3. Noise Thresholding and Consistency

To prevent the tree from growing infinitely due to noise, a threshold (θ) is implemented. If a noisy count falls below this threshold, the branch is pruned. Furthermore, a post-processing step ensures logical consistency—for example, ensuring a child node does not have a higher count than its parent.

Key Insights: Balancing Errors

The most significant insight of APTB is that treating every trajectory prefix as a unique entity is inefficient. By aggregating nodes with similar frequencies, individuals are "hidden" within a group more effectively, requiring less total noise to achieve the same privacy guarantee.

The algorithm manages a critical trade-off: merging nodes reduces noise error (fewer noise injections) but introduces reconstruction error (loss of fine-grained distinction). APTB is designed to find the optimal balance between these two factors.

Conclusion and Future Work

The APTB method effectively limits the cumulative noise that typically ruins high-dimensional prefix trees, maintaining higher utility for data mining tasks compared to standard algorithms. However, the authors acknowledge that the current privacy budget allocation does not fully account for how the noise threshold (θ) influences tree height. Future work will focus on integrating this parameter directly into the budget allocation to further reduce waste and improve trajectory accuracy.

Summary updated

Abstract

Collection of user's location and trajectory information that contains rich personal privacy in mobile social networks has become easier for attackers. Network traffic control is an important network system which can solve some security and privacy problems. In this paper, we consider a network traffic control system as a trusted third party and use differential privacy for protecting more personal trajectory data. We studied the influence of the high dimensionality and sparsity of trajectory data sets based on the availability of the published results. Based on similarity point aggregation reconstruction ideas and a prefix tree model, we proposed a hybrid publishing method of differential privacy spatiotemporal trajectory data sets APTB.
BibTeX
@misc{han2018spatio,
  author = {Qilong Han and Qianqian Chen and Kejia Zhang and Xiaojiang Du and Nadra Guizani},
  title = {{Spatio-temporal Trajectory Dataset Privacy Based on Network Traffic Control}},
  year = {2018},
  eprint = {1804.02052},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.02052},
}
Figure