Semantic-aware dummy selection for location privacy preservation

Abstract

With the development of smart devices and mobile positioning technologies, location-based services (LBS) has become more and more popular. While enjoying the convenience and entertainments provided by LBS, users are vulnerable to the increased privacy leakages of locations as another kind of quasi-identifiers. Most existing location privacy preservation algorithms are based on region cloaking which blurs the exact position into a region, and hence prone to inaccuracies of query results. Dummy-based approaches for location privacy preservation proposed recently overcome the above problem, but did not consider the problem of location semantic homogeneity. In this paper, we propose the Dummy Selection on Maximizing Minimum Distance (MaxMinDistDS) and simplified MaxMinDistDS (SimpMaxMinDistDS) that take into account both semantic diversity and physical dispersion of locations. MaxMinDistDS solves this dual-objective optimization problem by a greedy approach of maximizing first semantic diversity and then physical dispersion, and SimpMaxMinDistDS solves a simplified problem of single-objective optimization by uniting the two objectives together in order to improve the efficiency. Besides, we introduce a simplified way of computing location semantic distances by establishing a location semantic tree (LST) based on the hierarchy of locations and transforming the semantic distance into hops between nodes in LST. The efficiency and effectiveness of the proposed algorithms have been validated by a set of carefully designed experiments. The experimental results also show that our algorithms significantly improve the privacy level, compared to other dummy-based solutions.