Differential privacy with semantic neighboring: a notion of privacy for personalization services

Abstract Many internet services are personalized to the interests of users. It is usually based on the user profile extracted from the log of interactions of the user with internet applications. The profile, however, may naturally reveal sensitive information about the user. Hence, users urge the applications to protect their privacy, although they are interested in getting personalization services as far as possible. To formulate such requirements, we propose differential privacy with semantic neighboring, which relies on a novel notion of neighboring datasets. Two datasets are essentially defined to be neighboring if one is obtained by eliminating the records from the other proportional to the extent to which the records are semantically related to what the user deems private. We also develop a Laplace mechanism for enforcing the privacy policies specified in this way. The main challenge in devising the mechanism is to decide on an effective definition of the sensitivity of a given query on log datasets so that the mechanism can arrive at higher levels of utility. The results of our experimental study demonstrate that the proposed mechanism can achieve acceptable privacy parameters while retaining the usefulness of the underlying personalization service.