Anonymization of moving objects databases by clustering and perturbation

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 , 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 image 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 image for moving objects databases. We first characterize the image problem, then we recall image (image), a method that we introduced in based on clustering and spatial perturbation. Starting from a discussion on the limits of image we develop a novel clustering method that, being based on EDR distance , has the important feature of being time-tolerant. As a consequence it perturbs trajectories both in space and time. The novel method, named image (image), is empirically shown to produce higher quality anonymization than image, at the price of higher computational requirements. Therefore, in order to make image 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 image are empirically evaluated in terms of data quality and efficiency, and thoroughly compared to their predecessor image. 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 image one. Experimental results over both real-world and synthetic mobility data confirm that, for a wide range of values of image and k, the relative distortion introduced by our anonymization methods is kept low. Moreover, the techniques introduced to make image scalable to large datasets, achieve their goal without giving up data quality in the anonymization process.