Releasing search queries and clicks privately Export

@inproceedings{citeulike:4387902, 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.}, address = {New York, NY, USA}, author = {Korolova, Aleksandra and Kenthapadi, Krishnaram and Mishra, Nina and Ntoulas, Alexandros}, booktitle = {WWW '09: Proceedings of the 18th international conference on World wide web}, citeulike-article-id = {4387902}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1526709.1526733}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1526709.1526733}, comment = {[Talk] Anonymyzing query logs by removing usernames and ips is not enough. Removing numbers/names/dates/locations/etc. Substitution ciphers are easy to break. Previous/future releases are useful for breaking privacy. Differential privacy [Dwork et al. 2006] if knowledge about a person is roughly equal if the person uses a search engine wrt if the person does not use the search engine. Click-graph (1) add random noise to query counts, and if the noisy query count exceeds a certain threshold, include the query. (2) allow each user to add at most d1 queries and at most d2 clicks to the data, ignore the rest. (3) for top 10 URLs for each query, if noisy edge count exceeds a threshold, include the link. Releasable: 2.5M queries. Check then if the data is sufficient for certain applications: 1. "Fear of ..." queries. 2. Keyword suggestion for ads, using the degraded click log. Only about 13\% of the keyword suggestions are lost. Future work: release more tail queries, e.g. by grouping queries by similarity.}, doi = {10.1145/1526709.1526733}, isbn = {978-1-60558-487-4}, keywords = {adversarial-ir, clicks}, location = {Madrid, Spain}, pages = {171--180}, posted-at = {2009-04-23 16:28:26}, priority = {0}, publisher = {ACM}, title = {Releasing search queries and clicks privately}, url = {http://dx.doi.org/10.1145/1526709.1526733}, year = {2009} }

TY - CONF ID - citeulike:4387902 L3 - citeulike-article-id:4387902 N2 - 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. CY - Madrid, Spain SN - 978-1-60558-487-4 AD - New York, NY, USA EP - 180 TI - Releasing search queries and clicks privately PB - ACM T2 - WWW '09: Proceedings of the 18th international conference on World wide web SP - 171 KW - adversarial-ir KW - clicks N1 - [Talk] Anonymyzing query logs by removing usernames and ips is not enough. Removing numbers/names/dates/locations/etc. Substitution ciphers are easy to break. Previous/future releases are useful for breaking privacy. Differential privacy [Dwork et al. 2006] if knowledge about a person is roughly equal if the person uses a search engine wrt if the person does not use the search engine. Click-graph (1) add random noise to query counts, and if the noisy query count exceeds a certain threshold, include the query. (2) allow each user to add at most d1 queries and at most d2 clicks to the data, ignore the rest. (3) for top 10 URLs for each query, if noisy edge count exceeds a threshold, include the link. Releasable: 2.5M queries. Check then if the data is sufficient for certain applications: 1. "Fear of ..." queries. 2. Keyword suggestion for ads, using the degraded click log. Only about 13% of the keyword suggestions are lost. Future work: release more tail queries, e.g. by grouping queries by similarity. AU - Korolova, Aleksandra AU - Kenthapadi, Krishnaram AU - Mishra, Nina AU - Ntoulas, Alexandros PY - 2009/// UR - http://dx.doi.org/10.1145/1526709.1526733 ER -