The offering of location based services requires an in‐depth knowledge of the subscriber’s whereabouts. Thus, without the existence of strict safeguards, the deployment of such services may easily breach user privacy. To address this issue, special algorithms are necessary that anonymize user location information prior to its release to the service provider of the telecom operator. In this paper, we extend existing work in historical K‐anonymity (1) by considering an underlying network of user movement and (2) by pushing the core functionality of the anonymizer into a spatiotemporal DBMS. The proposed scheme allows each individual to specify his/her anonymity requirements, involving a series of spatiotemporal regions that are considered as unsafe with respect to his/her privacy. When the user requests an LBS from within one of his unsafe regions, the anonymizer performs a spatial along with a temporal generalization of his request in order to protect the user’s privacy. If the generalization algorithm fails to provide the necessary anonymity, the system dynamically constructs a mix‐zone around the requester with the aim of unlinking his future requests from the previous ones. As the experimental results indicate, by utilizing the spatiotemporal capabilities of the used DBMS, the performance of the anonymizer improves when compared to existing work in historical K‐anonymity.
