# Trajectory Clustering and k-NN for Robust Privacy Preserving Spatiotemporal Databases
## 1 Introduction  
Nowadays, the rapid development of Internet-of-things and radio-frequency identification sensor systems [1], in combination with evolution in satellites and wireless communication technologies, enables the tracking of moving objects such as vehicles, animals, and people [2]. Through mobility tracking, we collect a huge number of data, which give us considerable knowledge. Moving objects keep a continuous trajectory, however, this is described by a set of discrete points acquired by sampling at a specific rate and time-stamps for a period [3]. A simple description of a trajectory is as a finite sequence of pairs of locations with time-stamp, which meets GIS (Geographical Information System) database [2]. In the real world, people activities constitute spatiotemporal trajectories that are recorded either passively or actively, and can be used in human behavior analysis. Some examples of active recording are the check-ins of a user in a location-based social network or a series of tagged photos in Flickr, as each photo has a location tag (where) and a time-stamp (when). Moreover, an example of passive recording are credit card transactions, as each transaction has a corresponding time-stamp and location id. Modern vehicles such as taxies, buses, vessels and aircrafts have been equipped with GPS (Global Positioning System) devices that enable reporting of time-stamped locations [2]. Therefore, real-life examples make moving object and trajectory data mining important. Animal scientists and biologists can study the moving animals trajectories, for example to understand their migratory traces, behavior and/or living conditions. Meteorologists, environmentalists, climatologists,and oceanographers collect trajectory data of natural phenomena, as they capture environmental and climate changes, can forecast weather, manage natural disasters (hurricanes) and protect the environment. In addition, trajectory data can be used in law enforcement (e.g., video surveillance) and traffic analysis to improve transportation networks. More to the point, the evolution of technology in the domain of mobile devices, in combination with positioning capabilities (e.g., GPS), pave the way to location-based applications such as Facebook and Twitter. Indeed, social media networking has thoroughly changed people's habits in each aspect of their life, from personal and social to professional. A GPS sensor allows users to periodically transmit their location to a location-based service provider (active recording) to retrieve information about proximate points. However, queries based on location may conceal sensitive information about an individual [4]. Therefore, the privacy and anonymity preserving problem of mobile objects remains an important issue, which was in this work. The above issues, along with the work in [5], motivated us to perform the research presented in this paper. Specifically, \(k\)-NN queries are applied on the trajectory data points of mobile users in cases with or without clustering. In both methods, mobile users are camouflaged by their \(k\) nearest neighbors, which constitute their \(k\)-anonymity set. In the case of clustering, the trajectory points of all users in each time-stamp are grouped based on K-means (on-line clustering) and \(k\)-NN queries are applied to find the indexes of \(k\) nearest neighbors of all users, inside the cluster they belong to. Irrespective of the method used, if \(k\) nearest neighbors indexes remain the same or vary at a low rate in time, it is difficult for an adversary to discover a mobile user based on history data. We experimented on how this set changes in cases with or without clustering for different combinations of dimensions (\(x\),\(y\),\(g\),\(v\)), which is the main contribution of this work. We provide an analysis of the effect of dimensions on \(k\)-anonymity method.