Discovering private trajectories using background information

Kaplan, Emre and Pedersen, Thomas Brochmann and Savaş, Erkay and Saygın, Yücel (2010) Discovering private trajectories using background information. Data and Knowledge Engineering (Sp. Iss. SI), 69 (7). pp. 723-736. ISSN 0169-023X

This is the latest version of this item.

[thumbnail of This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing)] PDF (This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing))

Download (354kB)


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 reconstructed 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
Additional Information: Document Type: Proceedings Paper -- 12th International Conference on Knowledge-Based Intelligent Information and Engineering Systems ; Zagreb, CROATIA, SEP 03-05, 2008
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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 22 Jun 2010 16:06
Last Modified: 25 Jul 2019 10:17

Available Versions of this Item

Actions (login required)

View Item
View Item