Uncertainty for Privacy and 2-Dimensional Range Query Distortion

Abstract.

In this work, we study the problem of privacy-preserving data publishing in moving objects databases. In particular, the trajectory of a mobile user on the plane is no longer a polyline
in a two-dimensional space, instead it is a two-dimensional surface of fixed width 2A_{min}, where A_{min} defines the semidiameter of the minimum spatial circular extent that must replace the real location of the mobile user on the XY-plane, in the anonymized (kNN) request. Since a malicious attacker can observe that during the time, many of the neighbours ids change except for a small number of users, the desired anonimity is not achieved and the whole system becomes vulnerable to attackers. Thus, we reinforce the privacy model by clustering the mobile users according to their motion patterns in (u, θ) plane, where u and θ define the velocity measure and the motion direction (angle) respectively. In this case the anonymized (kNN) request lookups neighbours, who belong to the same cluster with the mobile requester in (u, θ) space: So, we know that the trajectory of the k-anonymous mobile user is within this surface, but we do not know exactly where. We transform the surface’s boundary poly-lines to dual points and we focus on the information distortion introduced by this space translation. We develop a set of effiient spatio-temporal access methods and we experimentally measure the impact of information distortion by comparing the performance results of the same spatio-temporal range queries executed on the original database and on the anonymized one.

Keywords: Uncertainty, Privacy, Anonymity, Moving Objects Databases, Voronoi Clustering

Download: (PDF file)