PrivBasis: Frequent Itemset Mining with Differential Privacy

Summary: PrivBasis uses theta-basis sets to enable differentially private mining: any high-frequency itemset is contained in some basis. It privately constructs the basis and derives frequent itemsets efficiently, outperforming state-of-the-art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10559
Venue: VLDB
Year: 2012
Pagerank: 0.00010828328
Overall Rank: 1,421 | 90.26%
DOI: 10.14778/2350229.2350261

Incoming Non-self Citations Over Time

Authors

1. Ninghui Li (Purdue University)
2. Wahbeh Qardaji (Purdue University)
3. Dong Su (Purdue University)
4. Jianneng Cao (Purdue University)

BibTeX Citation

@article{li_vldb12,
        title = {{PrivBasis: Frequent Itemset Mining with Differential Privacy}},
        author = {Li, Ninghui and Qardaji, Wahbeh and Su, Dong and Cao, Jianneng},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {11},
        pages = {1340--1351},
        doi = {10.14778/2350229.2350261},
        url = {https://doi.org/10.14778/2350229.2350261},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,169	PrivBayes: Private Data Release via Bayesian Networks	2014	SIGMOD	0.00011838753
1,308	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011216361
1,583	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010292522
2,074	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.2192882e-05
2,366	On Differentially Private Frequent Itemset Mining	2013	VLDB	8.6866148e-05
4,029	Differential Privacy in Telco Big Data Platform	2015	VLDB	6.946445e-05
4,837	PrivateClean: Data Cleaning and Differential Privacy	2016	SIGMOD	6.4845444e-05
5,055	APEx: Accuracy-Aware Differentially Private Data Exploration	2019	SIGMOD	6.3824509e-05
5,538	Mining Frequent Patterns with Differential Privacy	2013	VLDB	6.1819133e-05
5,613	Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges	2017	SIGMOD	6.1501263e-05
5,763	LDPTrace: Locally Differentially Private Trajectory Synthesis	2023	VLDB	6.0955612e-05
6,370	Differential Privacy in the Wild: A tutorial on current practices & open challenges	2016	VLDB	5.8973335e-05
6,772	PrivGene: Differentially Private Model Fitting Using Genetic Algorithms	2013	SIGMOD	5.7782652e-05
8,707	Set-valued Data Publication with Local Privacy: Tight Error Bounds and Efficient Mechanisms	2020	VLDB	5.3804383e-05
8,719	DPXPlain: Privately Explaining Aggregate Query Answers	2023	VLDB	5.3774243e-05
10,484	Privacy Loss of Noise Perturbation via Concentration Analysis of A Product Measure	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031639377
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
130	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030604781
510	Practical Privacy: The SuLQ Framework	2005	PODS	0.00017220509
711	Beyond Market Baskets: Generalizing Association Rules to Correlations	1997	SIGMOD	0.00014713746
1,817	On k-Anonymity and the Curse of Dimensionality	2005	VLDB	9.6832973e-05
2,856	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	8.0321774e-05
3,232	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.6179491e-05
4,344	Anonymization of Set-Valued Data via Top-Down, Local Generalization	2009	VLDB	6.7522581e-05
5,494	rho-uncertainty: Inference-Proof Transaction Anonymization	2010	VLDB	6.1997164e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,997	Mining Frequent Itemsets with Bit Strings and Trie	2002	VLDB
2	4,683	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB
3	9,212	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS
4	12,882	Mining Frequent Itemsets Using Support Constraints	2000	VLDB
5	7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD
6	12,150	Beyond Itemsets: Mining Frequent Featuresets over Structured Items	2015	VLDB
7	3,232	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
8	2,856	Publishing Set-Valued Data via Differential Privacy	2011	VLDB
9	5,538	Mining Frequent Patterns with Differential Privacy	2013	VLDB
10	2,366	On Differentially Private Frequent Itemset Mining	2013	VLDB