Publishing Search Logs—A Comparative Study of Privacy Guarantees

By M. Götz, Ashwin Machanavajjhala, Guozhang Wang, Xiaokui Xiao, Johannes Gehrke. 2009

114 citations recorded by the source corpus.

Search engine companies collect the “database of intentions,” the histories of their users' search queries. These search logs are a gold mine for researchers. Search engine companies, however, are wary of publishing search logs in order not to disclose sensitive information. In this paper, we analyze algorithms for publishing frequent keywords, queries, and clicks of a search log. We first show how methods that achieve variants of k-anonymity are vulnerable to active attacks. We then demonstrate that the stronger guarantee ensured by ε-differential privacy unfortunately does not provide any utility for this problem. We then propose an algorithm ZEALOUS and show how to set its parameters to achieve (ε, δ)-probabilistic privacy. We also contrast our analysis of ZEALOUS with an analysis by Korolova et al. [17] that achieves (ε',δ')-indistinguishability. Our paper concludes with a large experimental study using real applications where we compare ZEALOUS and previous work that achieves k-anonymity in search log publishing. Our results show that ZEALOUS yields comparable utility to k-anonymity while at the same time achieving much stronger privacy guarantees.

Subfields: Artificial Intelligence, Sociology and Political Science

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

Citations in the corpus

BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “For example, [24, 26, 16, 31] address the problem of publishing a subset of the data contained in a search log with differential privacy guarantees; [27] and [6] propose approaches for frequent item identification; [14] propose an approach for monitoring aggregated web browsing activities; and so on”
Functional Mechanism: Regression Analysis under Differential Privacy (2012, background): “This relaxed notion is useful in the scenarios where ϵ -differential privacy is too strict to allow any meaning results to be released (see [12, 15] for examples).”
Differentially private data cubes: optimizing noise sources and consistency (2011, methodology): “For example, the notion of DP has been applied to releasing query and click histograms from search logs [18, 22], recommender systems [29], publishing commuting patterns [27], publishing results of machine learning [6, 8, 20], clustering [13, 30], decision tree [14], mining frequent patterns [5], an”
Differentially Private SQL with Bounded User Contribution (2019, methodology): “Our work is not the first to use noise and thresholding to preserve privacy: this method was originally proposed in [17, 25] in the specific context of releasing search logs with (ε, δ)-DP; our work can be seen as an extension and generalization of this insight.”
Protecting privacy when mining and sharing user data (2012, methodology): “The work of [69] takes a similar approach to ours, utilizing two thresholds, and addition of noise to query counts, in order to determine which queries can be published.”
Differential Privacy via Wavelet Transforms (2009, background): “[19], [20], [21] for data publishing algorithms based on similar ideas.”