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.
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.
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