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-anonymity 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 kNN 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.