k-scale: k-Anonymizing Millions of Trajectories

Trajectory datasets collected by network operators and service providers offer detailed information about individual mobility and have wide application in business and research. However, managing such data raises privacy risks, as the unique movement patterns of individuals pose significant re-identification risks and make common countermeasures like pseudonymization ineffective. The privacy-preserving data publishing (PPDP) of trajectory datasets that maintains post-anonymization accuracy and truthfulness is an open problem -especially for large datasets with millions of records like those gathered by major actors in the telco ecosystem. We close this gap with k-scale, a framework that implements k-anonymity in massive mobile user trajectory datasets, removing uniqueness while safeguarding accuracy at the record level. Not only k-scale is the first model capable of scaling k-anonymization to a dataset of one million trajectories, but it does so while also outperforming state-of-the-art methods for trajectory data publishing in terms of preserved data quality, which we prove in real-world massive datasets and applications.