The research on search log anonymization is ten years old. Over this time, a number of methods to reduce the risks of user identification and disclosure of sensitive information from search log analysis have been proposed. However, the impact of these findings on the behaviour of data owners and publishers has been very limited so far. In this paper, we present a brief overview and a classification of the main approaches in the literature, arguing that there has been a shift towards a more pragmatic balance between the value of the data published and the risk of an adversary breaching the user's privacy. Then we go on to discuss what are the critical issues that must be tackled before search log anonymization moves out of research laboratories and into operational settings. We also clarify some misconceptions and mistakes in the use of the AOL search query log dataset, which is the main (and virtually only) experimental data source in the field.
Search log data are extremely valuable for a number of applications but pose
privacy risks. The infamous 2006 AOL incident, in which a user was identified from
a search log with randomized user identifiers [
Despite such advances, the collectors of search log data have been reluctant to publish them for new data users. Ten years later the AOL incident, academic researchers continue to use copies of the AOL search query dataset, downloaded from mirror sites. One partial exception of which we are aware is represented by the datasets made available at the Workshops on Web Search Click Data in recent WSDM conferences, which are meant for evaluating search log mining algorithms and are thus fully anonymized (i.e., everything is a number). The concerns about publishing user data combined with a lack of mature privacy preserving information retrieval techniques have affected not only the research on search log analysis but also on other related tasks such as medical information retrieval and microblog retrieval [31].
In this paper we present a review of ten year research on query log privacy,
including a fine classification and a discussion of key open problems. The only
earlier survey of which we are aware of is [
The remaining of the paper has the following structure. We first review the main sanitization methods, followed by a discussion of empirical evaluation of utility and privacy, and by a classification of approaches. Then we point out some open problems and presents the study concerning the AOL query log. We finally provide some conclusions. 2
Each record in a query log usually has the structure shown in Table 1. In this section we discuss how several methods delete or modify some of the efilds in Table 1 to produce a sanitized query log that better protects the user’s personal information. It is important to note that query log privacy is closely related to the older efild of database privacy [12] – from which many concepts and frameworks have been borrowed and adapted – but has unique features. In databases, records are described by the same (numerical or categorical) attributes, a restricted set of which are manually labeled as quasi-identifiers (e.g., postal code, age, gender) or sensitive (e.g., salary, diseases, political views). By contrast, in search logs, we have very large sparse data (i.e., the query content), where every item is potentially quasi-identiefir or sensitive. This approach consists of replacing well-established external identifiers (such as the user’s IP address and/or cookie ID) with a numerical ID, through hashing or randomization, while the query content remains the same. It prevents certain types of privacy leaks such as when an IP in a query log record is correlated with the same IP in some web service, but it can be broken in a relatively easy manner, because the queries of a user are gathered and their contents remain unchanged. Thus, as witnessed by the AOL incident, the data for identifying a user and discover sensitive information can be found in her queries. Because both the user-query association and the query content are maintained, the sanitized log has a high utility. 2.2
A simple approach to query log privacy is to delete the full IP addresses and cookie IDs, thus removing the explicit association between queries and users. This is a powerful tool in protecting user privacy, although there are other information (e.g., the user’s browser and operating system congfiurations, timestamps, and query content) that can still be used to associate multiple queries with the same user. Also, even single queries may be detrimental to privacy if users query their own personal information. On the utility side, this approach does not permit several log analysis application. 2.3
Hashing can be applied not only to external identifiers but also to single queries or elementary tokens within a query. This approach greatly helps to protect privacy because the original query is removed from the logs, although it may be possible to reverse-engineer particular query replacements by leveraging a statistical analysis of query frequencies gained from other available data sets [22]. The utility of the sanitized log is however clearly limited as most applications rely on the query content. 2.4
The idea is to form clusters of at least k users that are similar in terms of their data, and then make all the users in a cluster indistinguishable from each other. Only the clusters are released, each with its own set of queries. Various similarity measures and clustering algorithms have been proposed.
In [16], agglomerative clustering is performed using a bipartite graph built from the queries and the click-through data. Then they create a set of queries for each cluster by adding similar query objects and deleting dissimilar query objects. In [28], they use microaggregation, with a distance function that integrates various types of query log data; e.g., query content, timestamps, clicked URLs. The queries released for each cluster are the centroid of the cluster. Divisive hierarchical clustering driven by WordNet is used in [15], inspired by a similar approach developed for set-valued data [33]. A user’s queries are first generalized to the WordNet root concepts and then all the generalized prolfie queries are recursively partitioned top-down using more specific WordNet concepts to form the subpartitions, until no more partitions with clusters larger than k can be generated. The queries describing the clusters in the most specific partition are released. Another approach is [26], that works at the level of single terms and clusters users based on the similarity of their vocabularies, where the similarity between a pair of terms is topologically measured over a semantic network (e.g., WordNet) containing the terms.
These methods significantly reduce the risk of information disclosure when multiple relatively frequent queries are taken together. However, clustering rearranges the query log destroying the query ordering and creating fictitious sets of queries, which affects the utility of sanitized logs. 2.5
One of the most fundamental concepts developed in the privacy field is
kanonymity, extensively studied in the the database community to prevent
reidentification by multiple databases linking. It is assumed that a subset of
attributes are quasi-identiefirs and a record is released only if there are at least
other k-1 records that share the same values for those attributes, which is
usually achieved through generalization and suppression of attribute values [32].
As already remarked, query logs are fundamentally different from set-valued or
relational data because there is no explicit distinction between quasi-identifiers
and other types of information. Thus, the application of k-anonymity to search
query logs [
A query log L satisfies k-anonymity if for every query in L there exist at least k-1 identical queries in L issued by distinct users.
In this way, there is at most 1/k probability to link a query to a specific individual. However, this method leads to extreme data loss; e.g., about 90% of distinct AOL search log queries were issued by a single user.
To address the limitations of strict k-anonymity, one can try to protect a
query with semantically similar rather than equal queries. Adapting earlier work
on using WordNet to form privacy-enhanced user clusters [15], in [
Another variant of k-anonymity is kΘ -affinity ([
The enhanced versions of k-anonymity mitigate the data loss but are still unable to prevent the practical possibility of user identicfiation through combination of multiple, relatively frequent queries. For example, by entering in a search engine like Google the main research interest of the rfist author of this paper (i.e., web search) and his affiliation, one gets his name several times in the first results page. 2.6
Personal identifying information such as personal name, email, birth date, address, credit card number, social insurance number, phone number, and others, can be automatically detected and removed from the original query log using several established tecniques such as named entity recognition and relation extraction; see e.g., [20]. However, a query log anonymized by removing certain entities may still be very vulnerable to privacy attacks. Jones et al. [19] showed that a simple classifier trained with registered Yahoo! users can map a sequence of AOL queries without names and numbers into the gender, age, location of the user issuing the queries, thus facilitating user identification.
Machine learning is indeed a viable technology for an adversary to discover leaked sensitive information, but the publisher can use the same means to suppress just those information predicted to be sensitive, thus reducing the potential for information disclosure. This is the approach taken in [23], which ensures a good protection against a state-of-the-art learning algorithm while retaining over 90% of the original data. 2.7
Differential privacy [
P r[A(L1) ∈ S] ≤ e P r[A(L2) ∈ S] + δ (1) where L1 and L2 are the two query logs, A is a differentially private algorithm, Range(A) is the output range of A, and S ⊆ Range(A).
Borrowing on this notion, a differentially private algorithm for publishing a query click graph was proposed in [21]. It consists of three main steps: (1) select a limited number of queries per user, (2) alter their frequencies by injecting Laplacian noise, (3) release only the queries with a frequency higher than a given threshold together with a noisy count of their clicked URLs.
Like k-anonymity, differential privacy does not modify the content of the
single queries, but it changes their frequency and remove the association between
queries and users.1 Differential privacy is not an absolute privacy guarantee,
but it is very general and powerful because no particular assumptions about
an adversary’s computational power or ability to access external data are
required. On the other hand, for a typical choice of its parameters, it results in the
1 The dieffrential privacy model does not explicitly rely on the k anonymity parameter,
although it can be modified in this direction [14].
suppression of all rare as well as relatively frequent queries, up to frequencies
of the order of hundreds [21]. Furthermore, the destruction of the association
between users and queries prevents some of the most interesting applications
of published search log data. In fact, the utility of differential privacy has been
deeply questioned [13] due to the huge involved data loss. A recent proposal
extends differential privacy to preserve associations between users and queries, but
it requires the specification of a particular objective function to be optimized
[17]. Another recent refinement is concerned with reducing the high amount of
noise that needs to be added to satisfy differential privacy for text databases,
via sensitivity control [
The utility of search logs is a broad concept, connected as it is to some benetfi
gained by analyzing the data. Some studies compare the performance of the
original and released logs on certain data mining tasks such as clustering [28],
or on some applications such as query substitution [13] and advertisement [
ILR = H(X) − H(Y )
H(X) ,
H(X) = − X p(x) · log p(x)
(2) x where X and Y represent, respectively, the set of original and released queries, and H is the entropy.
The need for similar global privacy measures is equally important, because
given two sanitized logs produced by different methods one cannot say in which
log the user privacy is more protected. One of the few global privacy measure is
the Prolfie Exposure Level (PEL), proposed in [
PEL =
I(X, Y ) H(X) · 100,
I(X, Y ) = X p(x|y) · p(y) · log x,y p(x|y) p(x) (3) where I(X, Y ) is the mutual information between X and Y . The ratio between mutual information and entropy is known in statistics as the uncertainty coefficient, and can be seen as a normalized mutual information. It gives a measure of the information that Y provides about X, normalized with respect to the information of X.
These measures compute some kind of difference between the set of a user’s
queries before and after sanitization, relating such a difference to the loss of
utility (or gain of privacy). However, all queries are treated in the same manner.
It is just the probability distribution of queries that matters, not their content.
While this general approach may be suitable for evaluating utility, in the intuitive
sense that low difference approximately preserves the value of the original data
over various usages,2 it does not seem very appropriate for privacy. To evaluate
the latter, we may be more interested in specific pieces of information that may
lead to identify an individual (or disclose their sensitive information), rather
than in the overall resemblance of the search logs. Take PEL for instance. It is
easy to imagine a situation where the same PEL value corresponds to search logs
with very different privacy risks, depending on whether potentially identifying
queries with suitable distributions are present or not. Furthermore, the use of
average measures for evaluating privacy can be questioned on the ground that
the privacy guarantees are individually enforced by the anonymization algorithm
(for an in-depth discussion of privacy versus utility measures for relational data
see [
In Table 2, we provide a classicfiation of the main methods described in Section 2 along several dimensions, including preservation of user-query association and order of queries, degree of empirical privacy and utility (discussed in Section 3), list of enabled search log applications, and computational efficiency. Each method has strengths and weaknesses. The best choice depends on the emphasis on protecting the user privacy or retaining as much utility as possible, especially if the published log is intended to support specicfi applications. 5
Lack of attack model. The database community has precisely defined several types of attacks (record linkage, attribute linkage, table linkage, probabilistic attack) and has provided anonymization techniques for each specific attack, e.g., k-anonymity [32], l-diversity [27], t-closeness [24]. In general, the available techniques can deal with only some of these attacks; see e.g. [12]. For query logs, the modelization of attacks is more vague. It is generally assumed that an attacker has unspecified background knowledge and inference abilities that may lead to user identicfiation and disclosure of sensitive information. Future work should focus on how to model a realistic, resource-limited adversary; e.g., in terms of machine learning or information retrieval tools used to discover or rank sensitive information.
Pragmatic privacy guarantees. We have seen that several recent approaches including variants of k-anonymity and differential privacy have tried 2 Note however that two logs with entirely dieffrent queries may well have the same entropy, thus yielding ILR = 0 and maximal empirical utility, where in fact the utility of one log relative to the other is null. This happens, for instance, if we use query hashing as a sanitization method. to trade better levels of utility for reduced formal privacy guarantees. As full de-identification may be theoretically impossible, an interesting open problem is to explicitly relate the privacy guarantees to the inference power of an attacker, with the goal of making information disclosure too hard or costly for him/her. A first step in this direction is provided in [23].
Evaluation methodologies. The sanitization models developed so far
enforce different privacy guarantees for different types of output. In addition, each
model comes with its own set of parameters. A direct comparison of their
results is thus very difficult. This issue is being addressed also in the database
field [
Experimental datasets. In addition to a lack of benchmarks for experimental evaluation of privacy-preserving algorithms, researchers are often confronted with the paucity of annotated natural language datasets containing sensitive information; e.g., for training classifiers. These datasets are difficult to build, although there are recent works that automate this process to some extent; e.g., [29], [30]. There are also ethical issues involved here. Using only public data and never attempting to indentify users may not be enough, because an adversary could borrow the methods used to assess the privacy risk of an individual to select who to target. Also, publishing explicitly-sensitive anonymous profiles for research purposes poses a risk that someone could attempt to identify the individuals behind those data. 5.1
The AOL search log data set was retracted by AOL soon after its release due to privacy concerns, but it can still be downloaded from mirror sites. Because it is the only large data set of this kind available for testing to academic researcher, it has been used in a number of experimental studies in the last years. However, we discovered that the data set statistics reported in the literature have been obtained using some hidden and somewhat counter-intuitive assumptions and are not precise, as explained below. The data set contains 36,389,567 lines of data, of the format shown in Table 3. The efild AnonID is an anonymous user ID number, Query and QueryTime are, respectively, the query issued by the user and the time at which the query was entered, and the last two efilds (i.e., ItemRank and ClickURL) are present only if the user clicked on a search result. They are, respectively, the rank and the URL of the clicked item. Turning to the data set statistics, it is generally reported3 that there are 21,011,340 instances 3 http://www.researchpipeline.com/mediawiki/index.php?title=AOL Search Query Logs . of new queries (i.e., number of queries with repetitions). However, it is not explained how repetitions are computed. The apparent underlying interpretation is that two identical consecutive queries entered by the same user are seen as just one occurrence of the query, regardless of whether the user has clicked on some results or not and of the elapsed time between the two queries. Even under this interpretation, however, the available statistics are not entirely correct. We found out that the true number is 21,011,338 (instead of 21,011,340) due to a formatting mistake in the original data, as explained below. In line 2,586,379 of file ‘user-ct-test-collection-08.txt’, the AnonID begins with an empty space (see the middle row in Table 3). As the preceding and following queries are identical queries by the same user (i.e., 9403684), the three queries should count for one when computing the statistics. With this caveat, the number of queries amounts to 21,011,338. By contrast, if we used a wrong syntactic check of AnonID equality, we would obtain 21,011,338 + 2 = 21,011,340, which is the commonly used statistic. The relevant portion of data is illustrated in table Table 3.
Aside from this mistake, the requirement of non-consecutiveness does not seem to model the user behavior well, because this implies for instance that two identical queries with an elapsed time of 24 hours count for 1, while two identical non consecutive queries with an elapsed time of 30 seconds count for 2. It seems more convenient to update the frequency count even when two identical queries are consecutive, provided that their query time is different. Under this new interpretation, the number of queries grows to 28,898,361. The correct complete statistics are reported in Table 4. We would also like to point out that there are some very long meaningless query terms entered by multiple users. For instance, there are 37 query terms with 50 characters or more entered by at least two users. One of the most surprising query term is that formed by exactly 500 hyphens, entered by 18 users. These data are difficult to explain. One hypothesis is that multiple user ids may have been erroneously associated with the same user. The research on query log privacy has produced in ten years a number of insights. In this paper we have discussed strengths and weaknesses of existing methods, arguing that there has been a shift towards a more pragmatic approach to balance privacy guarantees and utility of sanitized logs. Today there are techniques
36,389,567 lines of data 21,011,338 instances of new non-consecutive queries
(w/ or w/o click-through) 28,898,361 instances of new queries (w/ or w/o click-through) 7,887,022 requests for next page of results 19,442,629 user click-through events 16,946,938 queries w/o user click-through 10,154,742 unique (normalized) queries
657,426 unique user ID’s that retain most of the utility of the original log at the cost of a very small privacy risk, based on a more realistic assessment of the inferential abilities of an adversary. The question remains as to these advances will be able to affect the visible behavior of the search log data collectors in the next future. 12. B. C. M. Fung, K. Wang, R. Chen, and P. S. Yu. Privacy-preserving data publishing: A survey of recent developments. ACM Computing Surveys (CSUR), 42(4):31– 61, 2010. 13. M. Got¨z, A. Machanavajjhala, G. Wang, X. Xiao, and J. Gehrke. Publishing Search
Logs: A Comparative Study of Privacy Guarantees. TKDE, 24(3):520–532, 2012. 14. Feild H, J. Allan, and J. Glatt. CrowdLogging: distributed, private, and anonymous search logging. In SIGIR, pages 375–384, 2011. 15. Y. He and J. F. Naughton. Anonymization of SetValued Data via TopDown, Local
Generalization. In VLDB, pages 934–945, 2009. 16. Y. Hong, X. He, J. Vaidya, N. Adam, and V. Atluri. Eeffctive anonymization of query logs. In CIKM, pages 1465–1468, 2009. 17. Y. Hong, J. Vaidya, H. Lu, and M. Wu. Differentially private search log sanitization with optimal output utility. In Proceedings of EDBT 2012, pages 50–61, 2012. 18. Y. Hu, Y. Qian, H. Li, J. pei, and Q. Zheng. Mining Query Subtopics from Search
Log Data. In SIGIR, pages 305–314, 2012. 19. R. Jones, R. Kumar, B. Pang, and A. Tomkins. ‘I know what you did last summer’: query logs and user privacy. In CIKM, pages 909–914, 2007. 20. L. Korba, Y. Wang, L. Geng, R. Song, G. Yee, A. S. Patrick, S. Buffet, H. Liu, and Y. You. Private Data Discovery for Privacy Compliance in Collaborative Environments. In CDVE’08), pages 142–150. Springer, 2008. 21. A. Korolova, K. Kenthapadi, N. Mishra, and A. Ntoulas. Releasing search queries and click privately. In WWW, pages 171–180, 2009. 22. Ravi Kumar, Jasmine Novak, Bo Pang, and Andrew Tomkins. On anonymizing query logs via token-based hashing. In WWW, 2007. 23. B. Li, Y. Vorobeychik, M. Li, and B. Malin. Iterative Classification for Sanitizing Large-Scale Datasets. In Proceedings of the 2015 IEEE International Conference on Data Mining (ICDM ’15), pages 841–846, 2015. 24. N. Li, T. Li, and M. Venkitasubramaniam. t-closeness: Privacy beyond kanonymity and l-diversity. In ICDE, 2008. 25. T. Li and N. Li. On the tradeoff between privacy and utility in data publishing.
In 15th SIGKDD, pages 517–526. ACM Press, 2009. 26. J. Liu and K. Wang. Anonymizing bag-valued sparse data by semantic similaritybased clustering. Knowledge and Information Systems, 35(2):435–461, 2013. 27. A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-diversity:
Privacy beyond k-anonymity. In 22nd ICDE, 2006. 28. G. Navarro-Arribas, V. Torra, A. Erola, and J. Castella-Roca. User k-anonymity for privacy preserving data mining of query logs. IPM, 48:476–487, 2012. 29. S. T. Peddinti, A. Korolova, E. Bursztein, and G. Sampemane. Cloak and Swagger: Understanding Data Sensitivity Through the Lens of User Anonymity. In Proceedings of the 2014 IEEE Symposium on Security & Privacy (SP ’14), pages 493–508, 2014. 30. S.T. Peddinti, K. W. Ross, and J. Cappos. Finding Sensitive Accounts on Twitter: An Automated Approach Based on Follower Anonymity. To appear in the 10th International AAAI Conference on Web and Social Media (ICWSM), 2016. 31. Luo Si and Hui Yang. PIR 2014 The First International Workshop on PrivacyPreserving IR: When Information Retrieval Meets Privacy and Security. SIGIR Forum, 48(2):83–88, 2014. 32. L. Sweeney. k-Anonymity: A Model for Protecting Privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):557–570, 2002. 33. M. Terrovitis, N. Mamoulis, and P. Kalnis. Privacy-preserving Anonymization of Set-valued Data. In VLDB’08, Auckland, New Zeland, pages 115–125, 2008.