Locally Differentially Private Frequent Itemset Mining

By Tianhao Wang, Ninghui Li, Somesh Jha. 2018

198 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “Various data analytics and machine learning problems have been studied under LDP, such as probability distribution estimation [15], [23], [30], [32], [42], heavy hitter discovery [4], [7], [33], [39], frequent new term discovery [37], frequency estimation [5], [38], frequent itemset mining [40], mar”
Distributed Clustering in the Anonymized Space with Local Differential Privacy (2019, background): “The 1Bit and RAPPOR mechanisms have made great progress in some statistical areas such as mean estimation [22] and frequency estimation [23].”
Consistent and Accurate Frequency Oracles under Local Differential Privacy (2019, methodology): “Optimized Local Hashing (OLH) [36] deals with a large domain size d by first using a random hash function to map an input value into a smaller domain of size д, and then applying randomized response to the hash value in the smaller domain.”
Locally Differentially Private Heavy Hitter Identification (2017, background): “For example, mean estimation [11], [27], frequent itemset mining [29], [37], releasing marginals under LDP [10], [30], [41], key-value pair estimation [40], evolving data monitoring [15], [22], and empirical risk minimization [31], [32].”
Privacy at Scale: Local Differential Privacy in Practice (2018, background): “Very recent work [26] proposes a protocol that provides much better accuracy than LDPMiner within the same privacy constraints.”
Differential Privacy for Deep and Federated Learning: A Survey (2022, background): “This is a hot research topic where research work can be divided into two categories: 1) The first category is the works producing pre-processing datasets balancing between accuracy and privacy for a specific learning model, such as frequent itemset mining models [71], [96], [97], and classification ”
CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy (2018, background): “Previous works on LDP focus on estimating the frequencies of frequent values the user possesses [6, 7, 16, 30, 37–39].”
Locally Differentially Private Data Collection and Analysis (2019, background): “Current researches focus on many related problems under the LDP model, such as mean/frequency estimation [15, 39, 48], probability distribution estimation [22, 56, 47], heavy hitter identification [5, 41, 8], itemset mining [50], marginal distribution release [12, 60], and empirical risk minimizatio”
Practical and Robust Privacy Amplification with Multi-Party Differential Privacy (2019, background): “The application of OLH is crucial for the utility of other application such as heavy hitter identification [10] and frequent itemset mining [40], [48].”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, unknown): “Interesting work has been done in both theCDPmodel [8, 22, 30, 33, 34, 39, 54– 56, 58, 70, 71, 75, 85, 89, 90, 100–102, 104, 105, 107] and the LDP model [13, 32, 42, 44, 91, 95–97, 108].”
Calibrate: Frequency Estimation and Heavy Hitter Identification with Local Differential Privacy via Incorporating Prior Knowledge (2018, unknown): “Local differential privacy (LDP) [27], [5], [20], [22], [30], [3], [12], [13], [34], [29], [23], [8], [24], [14], [6], [28], [32], [35], [1], a privacy protection mechanism based on differential privacy [15], can address both challenges.”