  The discovery of frequent itemsets can serve valuable economic and research
purposes. Releasing discovered frequent itemsets, however, presents privacy
challenges. In this paper, we study the problem of how to perform frequent
itemset mining on transaction databases while satisfying differential privacy.
We propose an approach, called PrivBasis, which leverages a novel notion called
basis sets. A theta-basis set has the property that any itemset with frequency
higher than theta is a subset of some basis. We introduce algorithms for
privately constructing a basis set and then using it to find the most frequent
itemsets. Experiments show that our approach greatly outperforms the current
state of the art.
