Description

Frequent itemsets mining finds sets of items that frequently appear together in a database. However, publishing this information might have privacy implications. Accordingly, in this paper we are considering the problem of guaranteeing differential privacy for frequent itemsets mining. We measure the utility of a frequent itemsets mining algorithm by its likelihood to produce a complete and sound result where “completeness” requires the algorithm to include the “sufficiently” frequent itemsets and “soundness” needs the algorithm to exclude the “sufficiently” infrequent ones. In this paper, we study the problem of designing a differentially private FIM algorithm which can simultaneously provide a high level of data utility and a high level of data privacy. This task is very challenging due to the possibility of long transactions. A potential solution is to limit the cardinality of transactions by truncating long transactions. However, such approach might cause too much information loss and result in poor performance. To limit the cardinality of transactions while reducing the information loss, we argue that long transactions should be split rather than truncated. To this end, we propose a transaction splitting based differentially private FIM algorithm. We put forward a dynamic reduction method to dynamically reduce the amount of noise added to guarantee privacy during the mining process. Through formal privacy analysis, we show that our PFP-growth algorithm is ∈ -differentially private. Extensive experiments on real datasets illustrate that our PFP-growth algorithm substantially outperforms the state-of-the-art techniques.