Differentially private search log sanitization with optimal output utility

Yuan Hong, Jaideep Vaidya, Haibing Lu, Mingrui Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

Web search logs contain extremely sensitive data, as evidenced by the recent AOL incident. However, storing and analyzing search logs can be very useful for many purposes (i.e. investigating human behavior). Thus, an important research question is how to privately sanitize search logs. Several search log anonymization techniques have been proposed with concrete privacy models. However, in all of these solutions, the output utility of the techniques is only evaluated rather than being maximized in any fashion. Indeed, for effective search log anonymization, it is desirable to derive the outputs with optimal utility while meeting the privacy standard. In this paper, we propose utility-maximizing sanitization based on the rigorous privacy standard of differential privacy, in the context of search logs. Specifically, we utilize optimization models to maximize the output utility of the sanitization for different applications, while ensuring that the production process satisfies differential privacy. An added benefit is that our novel randomization strategy maintains the schema integrity in the output search logs. A comprehensive evaluation on real search logs validates the approach and demonstrates its robustness and scalability.

Original languageEnglish (US)
Title of host publicationAdvances in Database Technology - EDBT 2012
Subtitle of host publication15th International Conference on Extending Database Technology, Proceedings
Pages50-61
Number of pages12
DOIs
StatePublished - Jul 10 2012
Event15th International Conference on Extending Database Technology, EDBT 2012 - Berlin, Germany
Duration: Mar 27 2012Mar 30 2012

Publication series

NameACM International Conference Proceeding Series

Other

Other15th International Conference on Extending Database Technology, EDBT 2012
CountryGermany
CityBerlin
Period3/27/123/30/12

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Keywords

  • differential privacy
  • optimization
  • search logs

Cite this

Hong, Y., Vaidya, J., Lu, H., & Wu, M. (2012). Differentially private search log sanitization with optimal output utility. In Advances in Database Technology - EDBT 2012: 15th International Conference on Extending Database Technology, Proceedings (pp. 50-61). (ACM International Conference Proceeding Series). https://doi.org/10.1145/2247596.2247604