Abstract— In this paper we present an approach to support privacy in people-centric sensing. In particular, we propose a technique that allows a central authority to select a subset of users whose past positions provide a good coverage of a given area of interest, without explicitly georeferencing them. To achieve this goal, we propose an efficient algorithm to solve the well known, NP -complete Set Cover problem that does not require explicit knowledge of the sets, but only uses their compact, privacy preserving representations or sketches. We perform a thorough experimental analysis to evaluate the performance of the proposed technique and its sensitivity to a few key parameters using public data from real applications. Experimental results support the effectiveness of the proposed approach to efficiently produce accurate environmental or social maps, at the same time preserving users’ privacy.

Index Terms— People Centric Sensing, Data Privacy, Efficient Data Representation.

Cite:Luca Becchetti, Luca Filipponi, and Andrea Vitaletti , "Privacy support in people-centric sensing," Journal of Communications, vol. 7, no.8, pp.606-621, 2012. Doi: 10.4304/jcm.7.8.606-621