On Differentially Private Frequent Itemset Mining
The authors consider differentially private frequent itemset mining. They begin by exploring the theoretical difficulty of simultaneously providing good utility and good privacy in this task. While their analysis proves that in general this is very difficult, it leaves a glimmer of hope in that their proof of difficulty relies on the existence of long transactions (that is, transactions containing many items). Accordingly, they investigate an approach that begins by truncating long transactions, trading off errors introduced by the truncation with those introduced by the noise added to guarantee privacy. Experimental results over standard benchmark databases show that truncating is indeed effective.