Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/6284
Title: Anonymization of moving objects databases by clustering and perturbation
Authors: Abul, Osman
Bonchi, Francesco
Nanni, Mirco
Keywords: Moving objects databases
Trajectories
Anonymity
Uncertainty
Clustering
Issue Date: 2010
Publisher: Pergamon-Elsevier Science Ltd
Abstract: Preserving individual privacy when publishing data is a problem that is receiving increasing attention. Thanks to its simplicity the concept of k-anonymity, introduced by Samarati and Sweeney [1], established itself as one fundamental principle for privacy preserving data publishing. According to the k-anonymity principle, each release of data must be such that each individual is indistinguishable from at least k-1 other individuals. In this article we tackle the problem of anonymization of moving objects databases. We propose a novel concept of k-anonymity based on co-localization, that exploits the inherent uncertainty of the moving object's whereabouts. Due to sampling and imprecision of the positioning systems (e.g., GPS), 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 (k,delta)-anonymity for moving objects databases. We first characterize the (k,delta)-anonymity problem, then we recall NWA (Never Walk Alone), a method that we introduced in [2] based on clustering and spatial perturbation. Starting from a discussion on the limits of NWA we develop a novel clustering method that, being based on EDR distance [3], has the important feature of being time-tolerant. As a consequence it perturbs trajectories both in space and time. The novel method, named W4M (Wait for Me), is empirically shown to produce higher quality anonymization than NWA, at the price of higher computational requirements. Therefore, in order to make W4M scalable to large datasets, we introduce two variants based on a novel (and computationally cheaper) time-tolerant distance function, and on chunking. All the variants of W4M(1) are empirically evaluated in terms of data quality and efficiency, and thoroughly compared to their predecessor NWA.(2) Data quality is assessed both by means of objective measures of information distortion, and by more usability oriented measure, i.e., by comparing the results of (i) spatio-temporal range queries and (ii) frequent pattern mining, executed on the original database and on the (k,delta)-anonymized one. Experimental results over both real-world and synthetic mobility data confirm that, for a wide range of values of delta and k, the relative distortion introduced by our anonymization methods is kept low. Moreover, the techniques introduced to make W4M scalable to large datasets, achieve their goal without giving up data quality in the anonymization process. (C) 2010 Elsevier B.V. All rights reserved.
URI: https://doi.org/10.1016/j.is.2010.05.003
https://hdl.handle.net/20.500.11851/6284
ISSN: 0306-4379
1873-6076
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

SCOPUSTM   
Citations

113
checked on Sep 23, 2022

WEB OF SCIENCETM
Citations

82
checked on Sep 24, 2022

Page view(s)

38
checked on Dec 26, 2022

Google ScholarTM

Check

Altmetric


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