Discovering private trajectories using background information

Kaplan, Emre and Pedersen, Thomas Brochmann and Savaş, Erkay and Saygın, Yücel (2009) Discovering private trajectories using background information. (Accepted/In Press)

WarningThere is a more recent version of this item available.

PDF (This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing) and post-print (ie final draft post-refereeing) ; author cannot archive publisher's version/PDF) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Trajectories are spatio-temporal traces of moving objects which contain valuable information to be harvested by spatio-temporal data mining techniques. Applications like city traffic planning, identification of evacuation routes, trend detection, and many more can benefit from trajectory mining. However, the trajectories of individuals often contain private and sensitive information, so anyone who possess trajectory data must take special care when disclosing this data. Removing identifiers from trajectories before the release is not effective against linkage type attacks, and rich sources of background information make it even worse. An alternative is to apply transformation techniques to map the given set of trajectories into another set where the distances are preserved. This way, the actual trajectories are not released, but the distance information can still be used for data mining techniques such as clustering. In this paper, we show that an unknown private trajectory can be re-constructed using the available background information together with the mutual distances released for data mining purposes. The background knowledge is in the form of known trajectories and extra information such as the speed limit. We provide analytical results which bound the number of the known trajectories needed to reconstruct private trajectories. Experiments performed on real trajectory data sets show that the number of known samples is surprisingly smaller than the actual theoretical bounds.

Item Type:Article
Uncontrolled Keywords:Privacy, Spatio-temporal data, trajectories, data mining
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:12982
Deposited By:Erkay Savaş
Deposited On:26 Nov 2009 23:56
Last Modified:24 Jul 2019 09:49

Available Versions of this Item

Repository Staff Only: item control page