Efficient algorithms for K-anonymous location privacy in participatory sensing

Location privacy is an important concern in participatory sensing applications, where users can both contribute valuable information (data reporting) as well as retrieve (location-dependent) information (query) regarding their surroundings. $K$-anonymlty is an important measure for privacy to prevent the disclosure of personal data. In this paper, we propose a mechanism based on locality-sensitive hashing (LSH) to partition user locations into groups each containing at least $K$ users (called spatial cloaks). The mechanism is shown to preserve both locality and $K$-anonymity, We then devise an efficient algorithm to answer $k$ NN queries for any point in the spatial cloaks of arbitrary polygonal shape. Extensive simulation study shows that both algorithms have superior performance with moderate computation complexity.