An Efficient Approach for Spatial Trajectory Anonymization

Spatial trajectories are being extensively collected and utilized nowadays. When publishing trajectory datasets that contain identifiable information about individuals, it is critically important to protect user privacy against linking attack. Although k-anonymity has been proven as a powerful tool to tackle trajectory re-identification, there still exists a significant gap in model efficiency, which severely impacts the feasibility of existing approaches for large-scale trajectory data. In this paper, we propose Gindex, a highly scalable solution for trajectory k-anonymization. It utilizes a hierarchical grid index and various optimization techniques to speed up k-clustering and trajectory merging. Extensive experiments on a real-life trajectory dataset verify the efficiency and scalability of Gindex which outperforms existing k-anonymity models by several orders of magnitude.