Abstract
The concept of location k-anonymity has been proposed to address the privacy issue of location based services (LBS). Under this notion of anonymity, the adversary only has the knowledge that the LBS request originates from a region containing at least k people, and therefore cannot individually distinguish the requestor. However, new types of LBS services such as continuous nearest neighbor searches require the knowledge of the user's trajectory, which can lead to a privacy breach. The longer the adversary can track the user's trajectory, the stronger the possibility that the user's sensitive information is revealed. To alleviate this problem, we propose algorithms to optimally partition a continuous request into multiple LBS requests with shorter trajectories. This results in increased privacy due to the unlinking of different requests over time and has the added benefit of improving the overall quality of service since the anonymized regions are now smaller. Our experimental results show that significant privacy and QoS benefits can be achieved with nominal computational overhead.