Preserving anonymity of recurrent location-based queries

The anonymization of location based queries through the generalization of spatio-temporal information has been proposed as a privacy preserving technique. We show that the presence of multiple concurrent requests, the repetition of similar requests by the same issuers, and the distribution of different service parameters in the requests can significantly affect the level of privacy obtained by current anonymity-based techniques. We provide a formal model of the privacy threat, and we propose an incremental defense technique based on a combination of anonymity and obfuscation. We show the effectiveness of this technique by means of an extensive experimental evaluation.