Please use this identifier to cite or link to this item:
Title: Never Walk Alone: Uncertainty for anonymity in moving objects databases
Authors: Abul, Osman
Bonchi, Francesco
Nanni, Mirco
Keywords: [No Keywords]
Issue Date: 2008
Publisher: IEEE
Source: 24th IEEE International Conference on Data Engineering/ 1st International Workshop on Secure Semantic Web -- APR 07-12, 2008 -- Cancun, MEXICO
Series/Report no.: IEEE International Conference on Data Engineering
Abstract: Preserving individual privacy when publishing data is a problem that is receiving increasing attention. According to the kappa-anonymity principle, each release of data must be such that each individual is indistinguishable from at least kappa - 1 other individuals. In this paper we study the problem of anonymity preserving data publishing in moving objects databases. We propose a novel concept of kappa-anonymity based on co-localization that exploits the inherent uncertainty of the moving object's whereabouts. Due to sampling and positioning systems (e.g., GPS) imprecision, the trajectory of a moving object is no longer a polyline in a three-dimensional space, instead it is a cylindrical volume, where its radius delta represents the possible location imprecision: we know that the trajectory of the moving object is within this cylinder, but we do not know exactly where. If another object moves within the same cylinder they are indistinguishable from each other. This leads to the definition of (kappa, delta)-anonymity for moving objects databases. We first characterize the (kappa,delta)-anonymity problem and discuss techniques to solve it. Then we focus on the most promising technique by the point of view of information preservation, namely space translation. We develop a suitable measure of the information distortion introduced by space translation, and we prove that the problem of achieving (kappa,delta)-anonymity by space translation with minimum distortion is NP-hard. Faced with the hardness of our problem we propose a greedy algorithm based on clustering and enhanced with ad hoc pre-processing and outlier removal techniques. The resulting method, named NWA (Never Walk Alone), is empirically evaluated in terms of data quality and efficiency. Data quality is assessed both by means of objective measures of information distortion, and by comparing the results of the same spatio-temporal range queries executed on the original database and on the (kappa, delta)-anonymized one. Experimental results show that for a wide range of values of delta and kappa, the relative error introduced is kept low, confirming that NWA produces high quality (kappa,delta)-anonymized data.
ISBN: 978-1-4244-1836-7
ISSN: 1084-4627
Appears in Collections:Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Show full item record

CORE Recommender


checked on Sep 23, 2022


checked on Sep 24, 2022

Page view(s)

checked on Feb 6, 2023

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.