King's College London

Research portal

Apriori-based algorithms for km-anonymizing trajectory data

Research output: Contribution to journalArticlepeer-review

Giorgos Poulis, Spiros Skiadopoulos, Grigorios Loukidis, Aris Gkoulalas-Divanis

Original languageEnglish
Pages (from-to)165-194
JournalTransactions on Data Privacy
Issue number2
Accepted/In press12 Jun 2014
PublishedAug 2014


King's Authors


The proliferation of GPS-enabled devices (e.g., smartphones and tablets) and location-based social networks has resulted in the abundance of trajectory data. The publication of such data opens up new directions in analyzing, studying and understanding human behavior. However, it should be performed in a privacy-preserving way, because the identities of individuals, whose movement is recorded in trajectories, can be disclosed even after removing identifying information. Existing trajectory data anonymization approaches offer privacy but at a high data utility cost, since they either do not produce truthful data (an important requirement of several applications), or are limited in their privacy specification component. In this work, we propose a novel approach that
overcomes these shortcomings by adapting km-anonymity to trajectory data. To realize our approach, we develop three efficient and effective anonymization algorithms that are based on the apriori principle. These algorithms aim at preserving different data characteristics, including location distance and semantic similarity, as well as user-specified utility requirements, which must be satisfied to ensure that the released data can be meaningfully analyzed. Our extensive experiments using synthetic and real datasets verify that the proposed algorithms are efficient and effective at preserving data utility.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454