In this paper we consider the problem of anonymizing datasets in which each individual is associated with a set of items that constitute private information about the individual. Illustrative datasets include market-basket datasets and search engine query logs. We formalize the notion of k-anonymity for set-valued data as a variant of the k-anonymity model for traditional relational datasets. We define an optimization problem that arises from this definition of anonymity and provide O(klogk) and O(1)-approximation algorithms for the same. We demonstrate applicability of our algorithms to the America Online query log dataset.
In @cite_14 the authors study the problem of anonymizing market-basket data. They propose a notion of anonymity similar to @math -anonymity where a limit is placed on the number of private items of any individual that could be known to an attacker beforehand. The authors provide generalization algorithms to achieve the anonymity requirements. For example, an item milk' in a user's basket may be generalized to dairy product' in order to protect it. In contrast, the techniques we propose consider additions and deletions to the dataset instead of generalizations. Further, we demonstrate applicability of our algorithms to search engine query log data as well where there is no obvious underlying hierarchy that can be used to generalize queries.
@cite_14
2135930857
We present a new class of statistical de- anonymization attacks against high-dimensional micro-data, such as individual preferences, recommendations, transaction records and so on. Our techniques are robust to perturbation in the data and tolerate some mistakes in the adversary's background knowledge. We apply our de-anonymization methodology to the Netflix Prize dataset, which contains anonymous movie ratings of 500,000 subscribers of Netflix, the world's largest online movie rental service. We demonstrate that an adversary who knows only a little bit about an individual subscriber can easily identify this subscriber's record in the dataset. Using the Internet Movie Database as the source of background knowledge, we successfully identified the Netflix records of known users, uncovering their apparent political preferences and other potentially sensitive information.