1. Locally Differentially Private Frequent Itemset Mining 2018 DifferentialPrivacy Oakland
    Tianhao Wang and Ninghui Li and Somesh Jha
    [View PDF on ieeexplore.ieee.org]
    [Show BibTex Citation]

    author={T. {Wang} and N. {Li} and S. {Jha}},
    booktitle={2018 IEEE Symposium on Security and Privacy (SP)},
    title={Locally Differentially Private Frequent Itemset Mining},
    keywords={data mining;data privacy;privacy amplification property;PSFO;SVIM;set-valued LDP setting;privacy guarantee;differentially private frequent itemset mining;sampling step;sample based frequency oracles;local differential privacy;LDP frequent oracle protocol;Protocols;Privacy;Frequency estimation;Itemsets;Estimation;Standards;local differential privacy;frequent itemset mining},

The notion of Local Differential Privacy (LDP) enables users to respond to sensitive questions while preserving their privacy. The basic LDP frequent oracle (FO) protocol enables an aggregator to estimate the frequency of any value. But when each user has a set of values, one needs an additional padding and sampling step to find the frequent values and estimate their frequencies. In this paper, we formally define such padding and sample based frequency oracles (PSFO). We further identify the privacy amplification property in PSFO. As a result, we propose SVIM, a protocol for finding frequent items in the set-valued LDP setting. Experiments show that under the same privacy guarantee and computational cost, SVIM significantly improves over existing methods. With SVIM to find frequent items, we propose SVSM to effectively find frequent itemsets, which to our knowledge has not been done before in the LDP setting.