K_θ-affinity privacy: Releasing infrequent query refinements safely

摘要

Search log k-anonymization is based on the elimination of infrequent queries under exact matching conditions, usually at the cost of high data loss. We present a semantic approach to fc-anonymity, termed k_Θ-affinity, in which a query can be protected by affine rather than identical queries. Based on the observation that many infrequent queries can be seen as refinements of a more general frequent query, we develop a three-step privacy model. We first represent query concepts as probabilistically weighted n-grams and extract them from the search log data. We then expand the original log queries with such concepts, defining the affinity between two queries as the similarity of their expanded representations. Finally, after building the graph of Θ-affine queries (for a given threshold Θ), we find the generalized k-cores of this graph, which coincide with the sets of queries satisfying k_Θ-affinity privacy. Experimenting with the AOL dataset, we compare fc-anonymity under affinity to fc-anonymity under equality and under WordNet generalization. We show that k_Θ-affinity achieves similar levels of privacy while at the same time reducing the data losses to a great extent. We also discuss its sensitivity to attacks.