PrivBasis: Frequent Itemset Mining with Differential Privacy

By Ninghui Li, Wahbeh H. Qardaji, Dong Su, Jianneng Cao. 2012

196 citations recorded by the source corpus.

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 θ-basis set has the property that any itemset with frequency higher than θ 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.

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

BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “For example, [24, 26, 16, 31] address the problem of publishing a subset of the data contained in a search log with differential privacy guarantees; [27] and [6] propose approaches for frequent item identification; [14] propose an approach for monitoring aggregated web browsing activities; and so on”
Discrimination- and privacy-aware patterns (2015, methodology): “Step 4 constructs B that covers all maximal cliques in (F, P) (see Li et al. 2012 for details).”
PrivateClean: Data Cleaning and Differential Privacy (2016, background): “Differential privacy also has been studied in a number of different contexts in databases including indexing and set-valued queries [7,27,37].”
Locally Differentially Private Frequent Itemset Mining (2018, background): “There exist protocols to handle this in the classic DP setting [39], [26].”
Privacy for All: Ensuring Fair and Equitable Privacy Protections (2018, methodology): “The value chosen for by different models in the research are 0.01 or 0.1 and in some cases ln2 or ln3 (Bhaskar et al., 2010; Bonomi and Xiong, 2013; Friedman and Schuster, 2010; Li et al., 2012; Zeng et al., 2012).”
PrivBayes: private data release via bayesian networks (2014, background): “Even if the data is skewed in the domain space, i.e., there are some entries x[i] with high counts, such peaks are infrequent and so the vast majority of published values x∗[i] are useless.”
Differentially Private Frequent Sequence Mining (2016, methodology): “To evaluate the performance of the algorithms, we follow two widely used standard metrics: F-score [7], [11] and Relative Error (RE) [16].”
Differentially Private Event Sequences over Infinite Streams (2014, background): “There are also works that focus on other specialized scenarios, such as range-count queries [32, 8], query consistency [19], sparse data [9, 23], correlated queries [18, 21], frequent itemsets [33, 22], trajectories [20], minimization of relative error [31], and non-numerical query answers [26].”
Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges (2016, unknown): “, regression/classification [1, 5, 14, 23, 39, 41, 42] and itemset mining [29, 44]).”
Differentially Private Data Publishing and Analysis: A Survey (2017, methodology): “[61], [63], [64] and [62] tried to merge some candidates into groups using different methods.”
Differentially Private K-Means Clustering (2015, background): “Differentially private frequent itemset mining has been studied in [2, 17].”
Mining Frequent Patterns with Differential Privacy (2013, methodology): “In this setting, only few works have been proposed to mine frequent patterns [3, 16, 25].”
Differential Privacy in Telco Big Data Platform (2015, background): “…deﬁnition which ensures the outcome of any authenticated query/calculation to be insensitive to any individual record in the DB. DP is preferred due to its strong mathematical boundary of the leaked privacy and has been widely studied in the research community [6, 23, 35, 27, 11, 18, 38, 34].”
When Relaxations Go Bad: "Differentially-Private" Machine Learning (2019, unknown): “Some of the early data analytics works on frequent pattern mining [6,41], decision trees [22], private record linkage [31] and recommender systems [47] were able to achieve both high utility and privacy with (cid:15) settings close to 1.”
The Large Margin Mechanism for Differentially Private Maximization (2014, background): “Subsequent algorithms exploit other properties of itemsets or avoid directly finding the most frequent itemset [34, 27, 15, 8].”
Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy (2016, methodology): “In our experiments, we use the following two metrics to cover each aspect: Relative Error (RE) [25].”