Releasing search queries and clicks privately
- 20 April 2009
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 171-180
- https://doi.org/10.1145/1526709.1526733
Abstract
The question of how to publish an anonymized search log was brought to the forefront by a well-intentioned, but privacy-unaware AOL search log release. Since then a series of ad-hoc techniques have been proposed in the literature, though none are known to be provably private. In this paper, we take a major step towards a solution: we show how queries, clicks and their associated perturbed counts can be published in a manner that rigorously preserves privacy. Our algorithm is decidedly simple to state, but non-trivial to analyze. On the opposite side of privacy is the question of whether the data we can safely publish is of any use. Our findings offer a glimmer of hope: we demonstrate that a non-negligible fraction of queries and clicks can indeed be safely published via a collection of experiments on a real search log. In addition, we select an application, keyword generation, and show that the keyword suggestions generated from the perturbed data resemble those generated from the original data.Keywords
This publication has 14 references indexed in Scilit:
- A learning theory approach to non-interactive database privacyPublished by Association for Computing Machinery (ACM) ,2008
- Robust De-anonymization of Large Sparse Datasets2008 IEEE Symposium on Security and Privacy (SP 2008), 2008
- Private Data Analysis via Output PerturbationPublished by Springer Science and Business Media LLC ,2008
- Extracting semantic relations from query logsPublished by Association for Computing Machinery (ACM) ,2007
- Random walks on the click graphPublished by Association for Computing Machinery (ACM) ,2007
- On anonymizing query logs via token-based hashingPublished by Association for Computing Machinery (ACM) ,2007
- Our Data, Ourselves: Privacy Via Distributed Noise GenerationLecture Notes in Computer Science, 2006
- When Random Sampling Preserves PrivacyLecture Notes in Computer Science, 2006
- Calibrating Noise to Sensitivity in Private Data AnalysisLecture Notes in Computer Science, 2006
- Accurately interpreting clickthrough data as implicit feedbackPublished by Association for Computing Machinery (ACM) ,2005